Problem:

Problem C: Ball

Problem

$N$個のボールがあり、各ボールには色と価値が決められている。

ボールの色は$1$から$C$まで$C$種類存在し、各色ごとに選べるボールの数の上限が決められている。

ボールを全体で高々$M$個選ぶとき、得られる価値の合計を最大化せよ。

Input

入力は以下の形式で与えられる。

$N$ $M$ $C$
$l_1$ $l_2$ ... $l_C$
$c_1$ $w_1$
$c_2$ $w_2$
...
$c_N$ $w_N$

  入力はすべて整数で与えられる。

  1行目に$N$, $M$, $C$が空白区切りで与えられる。

  2行目に色$i$の選べるボールの数の上限$l_i$($1 \leq i \leq C$)が空白区切りで与えられる。

  3行目以降の$N$行にボール$i$の色$c_i$と価値$w_i$($1 \leq i \leq N$)が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  
$1 \leq M \leq N \leq 10^5 $

  
$1 \leq C \leq 10^5 $

  
$0 \leq l_i \leq N $

  
$1 \leq c_i \leq C $

  
$1 \leq w_i \leq 1000 $

Output

得られる価値の最大値を1行に出力せよ。

Sample Input 1

3 3 2
1 1
1 1
1 100
2 10

Sample Output 1

110

2番目と3番目のボールを選ぶのが最適である。

Sample Input 2

3 3 3
1 0 1
1 1
2 100
3 1

Sample Output 2

2

ある色のボールが一個も選べない場合もある。

Sample Input 3

22 7 26
11 14 15 3 11 7 16 17 1 4 2 19 4 14 16 16 3 13 17 12 7 11 2 20 12 22
6 10
1 3
13 1
16 5
4 1
20 7
18 4
26 6
9 1
12 2
21 1
21 7
18 1
14 5
24 5
6 1
3 1
2 5
21 2
7 6
10 9
15 7

Sample Output 3

52



Sample input:
3 3 2
1 1
1 1
1 100
2 10


Sample output:
110

Submission status: Wrong Answer

Solution code:
n, m, c = map(int, input().split())
l = (0,) + tuple(map(int, input().split()))
a = [0] * (c + 1)
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
for i in range(m):
    if a[w[i][0]] < l[w[i][0]]:
        v += w[i][1]
        a[w[i][0]] += 1
    if sum(a) == m:
        break
print(v)

Submission status: Time Limit Exceeded

Solution code:
n, m, c = map(int, input().split())
l = (0,) + tuple(map(int, input().split()))
a = [0] * (c + 1)
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
for i in range(n):
    if a[w[i][0]] < l[w[i][0]]:
        v += w[i][1]
        a[w[i][0]] += 1
    if sum(a) == m:
        break
print(v)

Submission status: Accepted

Solution code:
N, M, C = map(int, input().split())
*L, = map(int, input().split())
B = []
for i in range(N):
    c, w = map(int, input().split())
    B.append((w, c))
B.sort(reverse=1)

ans = 0
for w, c in B:
    if L[c-1] > 0:
        ans += w
        M -= 1
        if M == 0:
            break
        L[c-1] -= 1
print(ans)

Submission status: Accepted

Solution code:
N, M, C = map(int, input().split())
*L, = map(int, input().split())
BALL = [list(map(int, input().split())) for i in range(N)]
BALL.sort(key=(lambda x: x[1]), reverse=1)
ans = 0
for c, w in BALL:
    if L[c-1]:
        ans += w
        L[c-1] -= 1
        M -= 1
        if M == 0:
            break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
N, M, C = inpl()
L = {i+1:v for i, v in enumerate(inpl())}

balls = []
for _ in range(N):
    c, w = inpl()
    balls.append([w, c])

balls = sorted(balls, reverse=True)

i = 0
count = 0
ans = 0
for i in range(N):
    w, c = balls[i]
    if count == M:
        break
    if L[c] == 0:
        continue
    else:
        count += 1
        ans += w
        L[c] -= 1

print(ans)

Submission status: Accepted

Solution code:
N,M,C=map(int,input().split())

l=list(map(int, input().split()))
CW=[]

for i in range(N):
    cw=list(map(int,input().split()))
    CW.append(cw)

CW.sort(key=lambda x:x[1],reverse=True)

L=[0]*C
ans=0
count=0
for i in range(N):
    if L[CW[i][0]-1]<l[CW[i][0]-1]:
        ans+=CW[i][1]
        L[CW[i][0]-1]+=1
        count+=1
    if count==M: break

print(ans)

Submission status: Accepted

Solution code:
N,M,C = map(int,input().split())
colors = [int(l) for l in input().split()]
ball = []
#print(len(colors),colors)

for _ in range(0,N):
    c,w = map(int,input().split())
    ball.append([c,w])

ball.sort(key= lambda x:x[1]) #価値でソートした
ball.reverse()
#print(ball)

take = 0 #ボール取った
cost = 0 #合計金額
i = 0 #リストのナンバリング

while (take <= M - 1) and (i <= N - 1):
    if colors[ball[i][0] - 1] == 0:
        i += 1
        #print(i)
        continue
    else:
        cost = cost + ball[i][1]
        colors[ball[i][0] - 1] = colors[ball[i][0] - 1] -1
        take += 1
        i += 1
        #print(i)

print(cost)

Submission status: Accepted

Solution code:
n, m, c = map(int, input().split())
l = [0] + list(map(int, input().split()))
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
p = 0
for i in range(n):
    if l[w[i][0]]:
        l[w[i][0]] -= 1
        v += w[i][1]
        p += 1
        if p == m:
            break
print(v)

Submission status: Accepted

Solution code:
import heapq
n, m, c = map(int,input().split())
que = [[] for i in range(c + 1)]
can_buy = [0] + list(map(int,input().split()))
for i in range(n):
    c, w = map(int, input().split())
    heapq.heappush(que[c], w)
    if len(que[c]) > can_buy[c]:
        heapq.heappop(que[c])
line = [j for i in que for j in i]
line.sort()
ans = sum(line[-m:])
print(ans)

Submission status: Runtime Error

Solution code:
n, m, c = map(int, input().split())
l = (0,) + tuple(map(int, input().split()))
a = [0] * (c + 1)
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
p = 0
for i in range(n):
    if l[w[i][0]]:
        l[w[i][0]] -= 1
        v += w[i][1]
        p += 1
        if p == m:
            break
print(v)