Problem p03148 (python)

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import islice
import operator

N, K = map(int, input().split())
sushi = [tuple([i] + [int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = [None] * N
choosen_kind = set()
ci = 0
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen[ci] = x
        ci += 1
        choosen_kind.add(t)
        del left[i]

choosen = choosen[:min(ci, K)]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

cands = islice(left.values(), K)
fixed = islice(cands, K - len(choosen))
base += sum(d for _,_,d in fixed)

score = base + kinds**2

for cand in cands:
    if cand[2] <= choosen[-1][2]:
        break

    base_n = base
    base_n -= choosen[-1][2]
    base_n += cand[2]
    kinds_n = kinds - 1
    
    score_n = base_n + kinds_n**2
    if score_n > score:
        choosen.pop()
        base, kinds, score = base_n, kinds_n, score_n
    else:
        break

print(score)

Buggy submission (verdict: Runtime Error):
from itertools import islice
import operator

N, K = map(int, input().split())
sushi = [tuple([i] + [int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = [None] * K
choosen_kind = set()
ci = 0
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen[ci] = x
        ci += 1
        choosen_kind.add(t)
        del left[i]

choosen = choosen[:min(ci, K)]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

cands = islice(left.values(), K)
fixed = islice(cands, K - len(choosen))
base += sum(d for _,_,d in fixed)

score = base + kinds**2

for cand in cands:
    if cand[2] <= choosen[-1][2]:
        break

    base_n = base
    base_n -= choosen[-1][2]
    base_n += cand[2]
    kinds_n = kinds - 1
    
    score_n = base_n + kinds_n**2
    if score_n > score:
        choosen.pop()
        base, kinds, score = base_n, kinds_n, score_n
    else:
        break

print(score)

Buggy submission (verdict: Runtime Error):
import itertools
import operator

N, K = map(int, input().split())
sushi = [(i, *[int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = []
choosen_kind = set()
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen.append(x)
        choosen_kind.add(t)
        del left[i]

choosen.sort(key=operator.itemgetter(2), reverse=True)
choosen = choosen[:K]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

tl = list(itertools.islice(left.values(), K))
fixed = tl[:K - len(choosen)]
cands = tl[K - len(choosen):]
base += sum(d for _,_,d in fixed)

score = base + kinds**2

if cands:
    comp = []
    while cands and cands[0][2] > choosen[-1][2]:
        base_n = base
        base_n -= choosen[-1][2]
        base_n += cands[0][2]
        kinds_n = kinds - 1
        
        score_n = base_n + kinds_n**2
        if score_n > score:
            choosen = choosen[:-1]
            fixed += cands[0]
            cands = cands[1:]
            base, kinds, score = base_n, kinds_n, score_n
        else:
            break
print(score)