forked from anubhab91/CodeForces-5
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDuffAndMeat.py
More file actions
37 lines (26 loc) · 852 Bytes
/
DuffAndMeat.py
File metadata and controls
37 lines (26 loc) · 852 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
__author__ = 'Devesh Bajpai'
'''
https://codeforces.com/problemset/problem/588/A
Solution: A greedy approach can give a good solution to it. We would always want to buy at the cheapest rate so far.
Hence we keep track of that as we go through the list of quantities (a) and rates (p). The current quantity is multiplied
with that rate and added to the total.
Time Complexity: O(n)
'''
def solve(a, p, n):
if len(a) == 0:
return 0
minRateSoFar = p[0]
total = p[0] * a[0]
for i in xrange(1, n):
minRateSoFar = min(minRateSoFar, p[i])
total += minRateSoFar * a[i]
return total
if __name__ == "__main__":
n = int(raw_input())
a = []
p = []
for i in xrange(0,n):
a_i, p_i = map(int, raw_input().split(" "))
a.append(a_i)
p.append(p_i)
print solve(a, p, n)