Problem p03148 (python)

Fixed submission:
# coding:utf-8

import sys
import heapq
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()
sushi = [(d, t) for t, d in (LI() for _ in range(n))]
sushi.sort()
sushi.reverse()

# sushiを美味しいものからk個とる
umami_max = []  # 寿司の種類数が減らないように最低一つは別で確保
umami_sub = []  # 種類数を増やす時に捨てる候補(priority_queueで管理)
used = set()
for i in range(k):
    d, t = sushi[i]
    if t not in used:
        umami_max.append(d)
        used.add(t)
    else:
        heapq.heappush(umami_sub, d)

umami_1 = sum(umami_max)
umami_2 = sum(umami_sub)
sushi_v = len(used)
ans = umami_1 + umami_2 + sushi_v ** 2

for i in range(k, n):
    if len(umami_sub) == 0:  # 捨てる寿司の候補がない場合，満足度はこれ以上大きくならない
        break
    d, t = sushi[i]
    if t in used:
        continue
    used.add(t)
    umami_1 += d
    umami_2 -= heapq.heappop(umami_sub)  # 一番美味しくない寿司を消す
    sushi_v += 1
    ans = max(ans, umami_1 + umami_2 + sushi_v ** 2)

print(ans)

Buggy submission (verdict: Runtime Error):
# coding:utf-8

import sys
import heapq
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()
sushi = [(d, t) for t, d in (LI() for _ in range(n))]
sushi.sort()
sushi.reverse()

# sushiを美味しいものからk個とる
umami_max = []  # 寿司の種類数が減らないように最低一つは別で確保
umami_sub = []  # 種類数を増やす時に捨てる候補(priority_queueで管理)
used = set()
for i in range(k):
    d, t = sushi[i]
    if t not in used:
        umami_max.append(d)
        used.add(t)
    else:
        heapq.heappush(umami_sub, d)

umami_1 = sum(umami_max)
umami_2 = sum(umami_sub)
sushi_v = len(used)
ans = umami_1 + umami_2 + sushi_v ** 2

# 捨てる寿司の候補がない場合，満足度はこれ以上大きくならない
if len(umami_sub) == 0:
    print(ans)
    exit()

for i in range(k, n):
    d, t = sushi[i]
    if t in used:
        continue
    used.add(t)
    umami_1 += d
    umami_2 -= heapq.heappop(umami_sub)  # 一番美味しくない寿司を消す
    sushi_v += 1
    ans = max(ans, umami_1 + umami_2 + sushi_v ** 2)

print(ans)

Buggy submission (verdict: Runtime Error):
# coding:utf-8

import sys
import heapq
from collections import defaultdict, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()
sushi = [(d, t) for t, d in (LI() for _ in range(n))]
sushi.sort()
sushi.reverse()

umami_max = []
umami_sub = []
used = set()
for i in range(k):
    d, t = sushi[i]
    if t not in used:
        umami_max.append(d)
        used.add(t)
    else:
        heapq.heappush(umami_sub, d)

umami_1 = sum(umami_max)
umami_2 = sum(umami_sub)
sushi_v = len(used)
ans = umami_1 + umami_2 + sushi_v ** 2
for i in range(k, n):
    d, t = sushi[i]
    if t in used:
        continue
    used.add(t)
    umami_1 += d
    umami_2 -= heapq.heappop(umami_sub)
    sushi_v += 1
    ans = max(ans, umami_1 + umami_2 + sushi_v ** 2)

print(ans)