-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum_ad_revenue.py
39 lines (29 loc) · 1.28 KB
/
maximum_ad_revenue.py
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
38
39
# python3
from itertools import permutations
def max_dot_product_naive(first_sequence, second_sequence):
assert len(first_sequence) == len(second_sequence)
assert len(first_sequence) <= 10 ** 3
assert all(0 <= f <= 10 ** 5 for f in first_sequence)
assert all(0 <= s <= 10 ** 5 for s in second_sequence)
max_product = 0
for permutation in permutations(second_sequence):
dot_product = sum(first_sequence[i] * permutation[i] for i in range(len(first_sequence)))
max_product = max(max_product, dot_product)
return max_product
def max_dot_product(first_sequence, second_sequence):
assert len(first_sequence) == len(second_sequence)
assert len(first_sequence) <= 10 ** 3
assert all(0 <= f <= 10 ** 5 for f in first_sequence)
assert all(0 <= s <= 10 ** 5 for s in second_sequence)
total = 0
while first_sequence and second_sequence:
total += max(first_sequence) * max(second_sequence)
first_sequence.remove(max(first_sequence))
second_sequence.remove(max(second_sequence))
return total
if __name__ == '__main__':
n = int(input())
prices = list(map(int, input().split()))
clicks = list(map(int, input().split()))
assert len(prices) == len(clicks) == n
print(max_dot_product(prices, clicks))