codeforces #326 div 2 A. Duff and Meat(水）
A. Duff and Meat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Duff is addicted to meat! Malek wants to keep her happy for n days. In order to be happy in i-th day, she needs to eat exactly a__i kilograms of meat.
There is a big shop uptown and Malek wants to buy meat for her from there. In i-th day, they sell meat for p__i dollars per kilogram. Malek knows all numbers _a_1, ..., a__n and _p_1, ..., p__n. In each day, he can buy arbitrary amount of meat, also he can keep some meat he has for the future.
Malek is a little tired from cooking meat, so he asked for your help. Help him to minimize the total money he spends to keep Duff happy for_n_ days.
Input
The first line of input contains integer n (1 ≤ n ≤ 105), the number of days.
In the next n lines, i-th line contains two integers a__i and p__i (1 ≤ a__i, p__i ≤ 100), the amount of meat Duff needs and the cost of meat in that day.
Output
Print the minimum money needed to keep Duff happy for n days, in one line.
Sample test(s)
input
3<br></br>1 3<br></br>2 2<br></br>3 1
output
10
input
3<br></br>1 3<br></br>2 1<br></br>3 2
output
8
Note
In the first sample case: An optimal way would be to buy 1 kg on the first day, 2 kg on the second day and 3 kg on the third day.
In the second sample case: An optimal way would be to buy 1 kg on the first day and 5 kg (needed meat for the second and third day) on the second day.
做点水题换换脑子。。。
浙大月赛题已经做蒙了QAQ
这题很简单。。
扫的时候记得更新价钱的最小值就好了。
1<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
2</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> > File Name: code/cf/#326/A.cpp
3</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> > Author: 111qqz
4</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> > Email: rkz2013@126.com
5</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> > Created Time: 2015年10月22日 星期四 20时00分33秒
6</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
7<span style="color: #008080;"> 7</span>
8<span style="color: #008080;"> 8</span> #include<iostream>
9<span style="color: #008080;"> 9</span> #include<iomanip>
10<span style="color: #008080;">10</span> #include<cstdio>
11<span style="color: #008080;">11</span> #include<algorithm>
12<span style="color: #008080;">12</span> #include<cmath>
13<span style="color: #008080;">13</span> #include<cstring>
14<span style="color: #008080;">14</span> #include<<span style="color: #0000ff;">string</span>>
15<span style="color: #008080;">15</span> #include<map>
16<span style="color: #008080;">16</span> #include<<span style="color: #0000ff;">set</span>>
17<span style="color: #008080;">17</span> #include<queue>
18<span style="color: #008080;">18</span> #include<vector>
19<span style="color: #008080;">19</span> #include<stack>
20<span style="color: #008080;">20</span> #include<cctype>
21<span style="color: #008080;">21</span>
22<span style="color: #008080;">22</span> <span style="color: #0000ff;">#define</span> yn hez111qqz
23<span style="color: #008080;">23</span> <span style="color: #0000ff;">#define</span> j1 cute111qqz
24<span style="color: #008080;">24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
25<span style="color: #008080;">25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
26</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
27</span><span style="color: #008080;">27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
28</span><span style="color: #008080;">28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
29</span><span style="color: #008080;">29</span> typedef <span style="color: #0000ff;">double</span><span style="color: #000000;"> DB;
30</span><span style="color: #008080;">30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
31</span><span style="color: #008080;">31</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> N=1E5+<span style="color: #800080;">7</span><span style="color: #000000;">;
32</span><span style="color: #008080;">32</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> n;
33</span><span style="color: #008080;">33</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> a[N],p[N];
34</span><span style="color: #008080;">34</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
35</span><span style="color: #008080;">35</span> <span style="color: #000000;">{
36</span><span style="color: #008080;">36</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
37</span><span style="color: #008080;">37</span> freopen(<span style="color: #800000;">"</span><span style="color: #800000;">in.txt</span><span style="color: #800000;">"</span>,<span style="color: #800000;">"</span><span style="color: #800000;">r</span><span style="color: #800000;">"</span><span style="color: #000000;">,stdin);
38</span><span style="color: #008080;">38</span> <span style="color: #0000ff;">#endif</span>
39<span style="color: #008080;">39</span>
40<span style="color: #008080;">40</span> scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">n);
41</span><span style="color: #008080;">41</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < n ; i++) scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d %d</span><span style="color: #800000;">"</span>,&a;[i],&<span style="color: #000000;">p[i]);
42</span><span style="color: #008080;">42</span> <span style="color: #0000ff;">int</span> mi =<span style="color: #000000;"> inf;
43</span><span style="color: #008080;">43</span> <span style="color: #0000ff;">int</span> ans = <span style="color: #800080;">0</span><span style="color: #000000;"> ;
44</span><span style="color: #008080;">44</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < n ; i++<span style="color: #000000;">)
45</span><span style="color: #008080;">45</span> <span style="color: #000000;"> {
46</span><span style="color: #008080;">46</span> <span style="color: #0000ff;">if</span> (p[i]<<span style="color: #000000;">mi)
47</span><span style="color: #008080;">47</span> mi =<span style="color: #000000;"> p[i];
48</span><span style="color: #008080;">48</span>
49<span style="color: #008080;">49</span> ans += mi*<span style="color: #000000;">a[i];
50</span><span style="color: #008080;">50</span> <span style="color: #000000;"> }
51</span><span style="color: #008080;">51</span> cout<<ans<<<span style="color: #000000;">endl;
52</span><span style="color: #008080;">52</span>
53<span style="color: #008080;">53</span>
54<span style="color: #008080;">54</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
55</span><span style="color: #008080;">55</span> <span style="color: #000000;"> fclose(stdin);
56</span><span style="color: #008080;">56</span> <span style="color: #0000ff;">#endif</span>
57<span style="color: #008080;">57</span> <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
58</span><span style="color: #008080;">58</span> }
View Code