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
1 3 2 2 3 1
output
10
input
3
1 3 2 1 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/*************************************************************************
2> File Name: code/cf/#326/A.cpp
3> Author: 111qqz
4> Email: rkz2013@126.com
5> Created Time: 2015年10月22日 星期四 20时00分33秒
6************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int n;
33int a[N],p[N];
34int main()
35{
36#ifndef ONLINE_JUDGE
37freopen("in.txt","r",stdin);
38#endif
39
40scanf("%d",&n);
41for ( int i = 0 ; i < n ; i++) scanf("%d %d",&a[i],&p[i]);
42int mi = inf;
43int ans = 0 ;
44for ( int i = 0 ; i < n ; i++)
45{
46if (p[i]<mi)
47mi = p[i];
48
49ans += mi*a[i];
50}
51cout<<ans<<endl;
52
53
54#ifndef ONLINE_JUDGE
55fclose(stdin);
56#endif
57return 0;
58}