PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N food items, each providing vitamin type A_i and with cost B_i.
If you buy several food items, their total value equals C\cdot X - Y, where X is the number of distinct vitamin types among them and Y is their total cost.
Find the maximum possible total value of buying some items.
EXPLANATION:
Looking at the total value, we see that each distinct vitamin type adds C and each individual item subtracts its cost.
From this, we can see that it’s never optimal to buy two different items that provide the same vitamin.
This is because we can keep one of them and discard the other one; which won’t change the number of distinct vitamins bought but will reduce the cost instead, so the total value will only increase.
So, for each vitamin type, we’ll buy at most one item.
Clearly, if we do buy an item of some type, it should be the one with minimum cost.
Let \text{best}[x] denote the minimum cost of an item with type x.
This is easy to compute: initialize \text{best}[x] to some large value (for example 1000, since we know costs can’t exceed 100), and then for each i, update \text{best}[A_i] with B_i.
Now, for each x, buying its corresponding item will add C to the value and subtract \text{best}[x] from it, for a total change of C - \text{best}[x].
So, if \text{best}[x] \lt C this is a profit overall, otherwise it’s a loss.
The final answer is hence the sum of C - \text{best}[x] across all x for which \text{best}[x] \lt C.
You can avoid doing casework by noting that this is equivalent to taking \max(0, C - \text{best}[x]).
So, the answer is
TIME COMPLEXITY:
\mathcal{O}(N + 100) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
best = [200]*101
for i in range(n):
best[a[i]] = min(best[a[i]], b[i])
ans = 0
for i in range(101):
ans += max(0, c - best[i])
print(ans)