Problem p03148 (python)

Fixed submission:
# -*- coding: utf-8 -*-


n, k = map(int, input().split())

# Store data
sushis = []
neta_set = set()
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)


# Select sushi set as maximum oishisa point
sel_sushis = []
neta_set = set()
sum_oishisa = 0
for i in range(k):
    t, d = sushis.pop()
    if t in neta_set:
        sel_sushis.append((t,d))
    else:
        neta_set.add(t)
    sum_oishisa += d

sel_sushis.sort(key=lambda i:i[1], reverse=True)
tMin = len(neta_set)
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    if len(sel_sushis) == 0:
        break
    t1, d1 = sel_sushis.pop()
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    while True:
        t2, d2 = sushis.pop()
        if not t2 in neta_set:
            break

    sum_oishisa += d2
    neta_set.add(t2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)

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

def popMaxOishisa(sushis):
    t, d = sushis.pop()
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    t, d = -1, -1
    while True:
        t, d = sushis.pop()
        if not t in netas:
            break
    return t, d


n, k = map(int, input().split())

# Store data
sushis = []
neta_set = set()
sel_sushis = {"min":{}}
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis[t].append(d)
        if sel_sushis["min"][t] > d:
            sel_sushis["min"][t] = d
    sum_oishisa += d

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    if t1 < 0:
        break
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)

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

def popMaxOishisa(sushis):
    t, d = max(sushis["max"].items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"].pop(t)
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    max_dict = {k:v for k,v in sushis["max"].items() if not k in netas}
    t, d = max(max_dict.items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


n, k = map(int, input().split())

# Store data
sushis = {}
sel_sushis = {}
for i in range(n):
    t, d = map(int, input().split())
    if not t in sushis:
        sushis[t] = [d]
    else:
        sushis[t].append(d)

# Formatting
for type in sushis:
    sushis[type].sort()
sushis["max"] = {t:sushis[t][-1] for t in sushis}

tMax = len(sushis) - 1

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t1 in sushis:
        sushis[t1] = [d1]
    else:
        sushis[t1].append(d1)

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)

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

def popMaxOishisa(sushis):
    t, d = max(sushis["max"].items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"].pop(t)
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    max_dict = {k:v for k,v in sushis["max"].items() if not k in netas}
    t, d = max(sushis["max"].items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


n, k = map(int, input().split())

# Store data
sushis = {}
sel_sushis = {}
for i in range(n):
    t, d = map(int, input().split())
    if not t in sushis:
        sushis[t] = [d]
    else:
        sushis[t].append(d)

# Formatting
for type in sushis:
    sushis[type].sort()
sushis["max"] = {t:sushis[t][-1] for t in sushis}

tMax = len(sushis) - 1

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t1 in sushis:
        sushis[t1] = [d1]
    else:
        sushis[t1].append(d1)

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)