Problem p03148 (python)

Fixed submission:
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]            #  おいしさポイントの高い方からK個の寿司を選択
    pick_type = set([t for t, d in pick]) # 選択済の種類

    cnt = Counter()             #  各種類の寿司が何個ずつあるか覚えておく
    for t, d in pick:
        cnt[t] += 1

    rem = dict()                #  未選択の種類の寿司のうち、一番おいしさポイントが高い物
    for t, d in sushi:
        if t not in pick_type:
            rem[t] = max(rem.get(t, 0), d)
    res = sorted([[k, v] for k, v in rem.items()], key=lambda x: x[1]) # おいしさで昇順にソート(一番おいしい物が末尾)

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2] #  現在の選択でのスコア、ここから種類を1つずつ増加させていきスコアを計算する
    while len(pick_type) < K and pick and res:
        t, d = res.pop()
        pick_type.add(t)
        tt, dd = pick.pop()
        while cnt[tt] == 1 and pick:
            tt, dd = pick.pop()
        if cnt[tt] > 1:
            cnt[tt] -= 1
            manzoku = manzoku - dd + d
            ans.append(manzoku+ len(pick_type)**2)
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]
    pick_type = set([t for t, d in pick])

    cnt = Counter()
    for t, d in pick:
        cnt[t] += 1

    rem = dict()
    for t, d in sushi:
        if t not in pick_type:
            rem[t] = max(rem.get(t, 0), d)

    res = sorted([[k, v] for k, v in rem.items()], key=lambda x: x[1])

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2]
    while len(pick_type) < K:
        t, d = res.pop()
        pick_type.add(t)
        tt, dd = pick.pop()
        if cnt[tt] > 1:
            cnt[tt] -= 1
            manzoku = manzoku - dd + d
            ans.append(manzoku+ len(pick_type)**2)
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]
    pick_type = set([t for t, d in pick])

    cnt = Counter()
    for t, d in pick:
        cnt[t] += 1

    rem = dict()
    for t, d in sushi:
        if t not in pick_type:
            rem[t] = max(rem.get(t, 0), d)

    res = sorted([[k, v] for k, v in rem.items()], key=lambda x: x[1])

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2]
    while res:
        t, d = res.pop()
        pick_type.add(t)
        tt, dd = pick.pop()
        if cnt[tt] > 1:
            cnt[tt] -= 1
            manzoku = manzoku - dd + d
            ans.append(manzoku+ len(pick_type)**2)
    return max(ans)


def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
D - Various Sushi
https://atcoder.jp/contests/abc116/tasks/abc116_d

"""
import sys

from collections import Counter

def solve(N, K, sushi):
    sushi.sort(key=lambda x: x[1], reverse=True)
    pick = sushi[:K]
    rem = sushi[K:][::-1]
    all_type = set([t for t, d in sushi])
    pick_type = set([t for t, d in pick])

    cnt = Counter()
    for t, d in pick:
        cnt[t] += 1

    manzoku = sum([d for t, d in pick])
    ans = [manzoku + len(pick_type)**2]
    while pick_type != all_type:
        t, d = rem.pop()
        if t not in pick:
            pick_type.add(t)
            tt, dd = pick.pop()
            if cnt[tt] > 1:
                cnt[tt] -= 1
                manzoku = manzoku - dd + d
                ans.append(manzoku+ len(pick_type)**2)
    return max(ans)



def main(args):
    N, K = map(int, input().split())
    sushi = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, K, sushi)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])