NUTRITION - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh_07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have N fruits, the i-th is of type A_i and has nutrition B_i.
You can eat at most one of each type of fruit.
What’s the maximum nutrition you can attain?

EXPLANATION:

Since we can only eat at most one fruit of each type, clearly it’s best to eat the one with maximum nutrition.
Further, if this maximum nutrition is negative, it’s optimal to not eat any fruits of this type.

Let \text{mx} be an array of size N such that \text{mx}[x] denotes the maximum nutrition of a fruit of type x.
Initially, \text{mx}[x] = 0 for every x.
Then, for each i from 1 to N, set \text{mx}[A_i] to \max(B_i, \text{mx}[A_i]).

The overall answer is then just the sum of the \text{mx} array.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    mx = [0]*(101)
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(n): mx[a[i]] = max(mx[a[i]], b[i])
    print(sum(mx))