Problem p03148 (python)

Fixed submission:
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td = [(x[0]-1,x[1]) for x in td]
td.sort(key=lambda x:-x[1])

t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[:K]
for i in range(K):
    t[tdK[i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if d_top[td[i][0]] == 0:
        d_top[td[i][0]] = td[i][1]
    else:
        d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
s = sum(d_top)
ans = l**2 + s
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))

if len(d_rest) == 0:
    print(ans)
else:
    ans += d_rest_cum[-1]
    s += d_rest_cum[-1]
    for k in range(min(len(d_rest),len(d_candi))):
        ans = max((l+k+1)**2 + s + d_candi_cum[k] - d_rest_cum[k],ans)

    print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td.sort(key=lambda x:-x[1])
td = [(x[0]-1,x[1]) for x in td]
t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
tdK = td[td[:K]]
for i in range(K):
    t[tdK[i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if t[td[i][0]] == 1:
        if d_top[td[i][0]] == 0:
            d_top[td[i][0]] = td[i][1]
        else:
            d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])
l = len(t_used)
ans = l**2+sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))

if len(d_rest) == 0:
    print(ans)
else:
    ans += d_rest_cum[-1]

    for k in range(min(len(d_rest),len(d_candi))):
        ans = max(ans + (k+1)*(k+1+2*l) + d_candi_cum[k] - d_rest_cum[k],ans)

    print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td.sort(key=lambda x:-x[1])
td = [(x[0]-1,x[1]) for x in td]
t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
for i in range(K):
    t[td[:K][i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if t[td[i][0]] == 1:
        if d_top[td[i][0]] == 0:
            d_top[td[i][0]] = td[i][1]
        else:
            d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])

ans = len(t_used)**2+sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))
ans += d_rest_cum[-1]

for k in range(min(len(d_rest),len(d_candi))):
    ans = max(ans + (k+1)*(k+1+2*len(t_used)) + d_candi_cum[k] - d_rest_cum[k],ans)

print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
N,K = map(int,input().split())
td = [tuple(map(int,input().split())) for i in range(N)]

td.sort(key=lambda x:-x[1])
td = [(x[0]-1,x[1]) for x in td]
t = [-1]*N
for i in range(N):
    t[td[i][0]] = 0
for i in range(K):
    t[td[:K][i][0]] = 1

t_used = [i for i in range(N) if t[i]==1]
t_not_used = [i for i in range(N) if t[i]==0]

d_top = [0]*N
d_top_candi = [0]*N
d_rest = []
d_candi = []

for i in range(K):
    if t[td[i][0]] == 1:
        if d_top[td[i][0]] == 0:
            d_top[td[i][0]] = td[i][1]
        else:
            d_rest.append(td[i][1])
for i in range(K,N):
    if t[td[i][0]] == 0:
        if d_top_candi[td[i][0]] == 0:
            d_top_candi[td[i][0]] = 1
            d_candi.append(td[i][1])

ans = len(t_used)**2+sum(d_top)
d_rest.sort()
d_candi.sort(key=lambda x:-x)

d_rest_cum = list(accumulate(d_rest))
d_candi_cum = list(accumulate(d_candi))
ans += d_rest_cum[-1]

for k in range(min(len(d_rest),len(d_candi))):
    ans = max(ans + (k+1)*(k+1+2*len(t_used)) + d_candi_cum[k] - d_rest_cum[k],ans)

print(ans)