Cards and Joy (Codeforces 999F)
Tags: DP, dp

There are $$$n$$$ players sitting at the card table. Each player has a favorite number. The favorite number of the $$$j$$$-th player is $$$f_j$$$.There are $$$k \cdot n$$$ cards on the table. Each card contains a single integer: the $$$i$$$-th card contains number $$$c_i$$$. Also, you are given a sequence $$$h_1, h_2, \dots, h_k$$$. Its meaning will be explained below.The players have to distribute all the cards in such a way that each of them will hold exactly $$$k$$$ cards. After all the cards are distributed, each player counts the number of cards he has that contains his favorite number. The joy level of a player equals $$$h_t$$$ if the player holds $$$t$$$ cards containing his favorite number. If a player gets no cards with his favorite number (i.e., $$$t=0$$$), his joy level is $$$0$$$.Print the maximum possible total joy levels of the players after the cards are distributed. Note that the sequence $$$h_1, \dots, h_k$$$ is the same for all the players.

Input: The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 500, 1 \le k \le 10$$$) — the number of players and the number of cards each player will get.The second line contains $$$k \cdot n$$$ integers $$$c_1, c_2, \dots, c_{k \cdot n}$$$ ($$$1 \le c_i \le 10^5$$$) — the numbers written on the cards.The third line contains $$$n$$$ integers $$$f_1, f_2, \dots, f_n$$$ ($$$1 \le f_j \le 10^5$$$) — the favorite numbers of the players.The fourth line contains $$$k$$$ integers $$$h_1, h_2, \dots, h_k$$$ ($$$1 \le h_t \le 10^5$$$), where $$$h_t$$$ is the joy level of a player if he gets exactly $$$t$$$ cards with his favorite number written on them. It is guaranteed that the condition $$$h_{t - 1} < h_t$$$ holds for each $$$t \in [2..k]$$$.

Output: Print one integer — the maximum possible total joy levels of the players among all possible card distributions.

Note: In the first example, one possible optimal card distribution is the following:  Player $$$1$$$ gets cards with numbers $$$[1, 3, 8]$$$;  Player $$$2$$$ gets cards with numbers $$$[2, 2, 8]$$$;  Player $$$3$$$ gets cards with numbers $$$[2, 2, 8]$$$;  Player $$$4$$$ gets cards with numbers $$$[5, 5, 5]$$$. Thus, the answer is $$$2 + 6 + 6 + 7 = 21$$$.In the second example, no player can get a card with his favorite number. Thus, the answer is $$$0$$$.

Sample Inputs:
4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7

3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3

Sample Outputs:
21

0

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
c = list(map(int, input().split()))
f = list(map(int, input().split()))
h = [0] + list(map(int, input().split()))
cnt1 = defaultdict(lambda : 0)
for i in c:
    cnt1[i] += 1
cnt2 = defaultdict(lambda : 0)
for i in f:
    cnt2[i] += 1
ans = 0
for i in cnt2:
    (c1, c2) = (cnt1[i], cnt2[i])
    dp0 = [0]
    l = 1
    for _ in range(c2):
        dp = [0] * (l + k)
        for i in range(l):
            dp0i = dp0[i]
            for j in range(k + 1):
                dp[i + j] = max(dp[i + j], dp0i + h[j])
        l += k
        dp0 = dp
    ans += dp[min(c1, k * c2)]
print(ans)

Solution (Python):
(n, k) = map(int, input().split())
C = list(map(int, input().split()))
C = [c - 1 for c in C]
F = list(map(int, input().split()))
F = [f - 1 for f in F]
H = list(map(int, input().split()))
H = [0] + H
from collections import Counter
C = Counter(C)
F = Counter(F)
dp = [[0] * (k * n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(n * k):
        for l in range(k + 1):
            if j + l <= k * n:
                dp[i + 1][j + l] = max(dp[i + 1][j + l], dp[i][j] + H[l])
ans = 0
for c in C.keys():
    ans += dp[F[c]][C[c]]
print(ans)

Solution (Python):
from collections import Counter
(n, k) = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
f = [int(x) for x in input().split()]
h = [0] + [int(x) for x in input().split()]
cnt_all = Counter(c)
cnt_fav = Counter(f)
ans = 0
for fi in cnt_fav:
    if fi not in cnt_all:
        continue
    m = cnt_fav[fi]
    t = min(cnt_all[fi], m * k)
    dp = [[0] * (t + 1) for _ in range(m + 1)]
    for x in range(1, m + 1):
        for s in range(0, t + 1):
            for ki in range(0, k + 1):
                if ki + s > t:
                    break
                dp[x][ki + s] = max(dp[x][ki + s], dp[x - 1][s] + h[ki])
    ans += dp[m][t]
print(ans)