Problem p03148 (python)

Fixed submission:
N, K = map(int, input().split())
umai = {}
mazui = []
for _ in range(N):
    t, d = map(int, input().split())
    if t not in umai:
        umai[t] = d
    else:
        tmp = umai[t]
        if tmp < d:
            umai[t] = d
            mazui.append((t, tmp))
        else:
            mazui.append((t, d))

umai = sorted(umai.items(), key=lambda x: -x[1])
mazui = sorted(mazui, key=lambda x: -x[1])


umai_len = len(umai)
mazui_len = len(mazui)

acc_umai = [0 for _ in range(umai_len)]
acc_umai[0] = umai[0][1]
for i in range(umai_len - 1):
    acc_umai[i + 1] = acc_umai[i] + umai[i + 1][1]

acc_mazui = [0 for _ in range(mazui_len)]
if mazui_len > 0:

    acc_mazui[0] = mazui[0][1]
    for i in range(mazui_len - 1):
        acc_mazui[i + 1] = acc_mazui[i] + mazui[i + 1][1]
acc_mazui.insert(0, 0)

ans = []
for i in range(1, K + 1):
    if umai_len < i or mazui_len < K - i:
        continue
    ans.append(acc_umai[i - 1] + acc_mazui[K - i] + i ** 2)
print(max(ans))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
umai = {}
mazui = []
for _ in range(N):
    t, d = map(int, input().split())
    if t not in umai:
        umai[t] = d
    else:
        tmp = umai[t]
        if tmp < d:
            umai[t] = d
            mazui.append((t, tmp))
        else:
            mazui.append((t, d))

umai = sorted(umai.items(), key=lambda x: -x[1])
mazui = sorted(mazui, key=lambda x: -x[1])


umai_len = len(umai)
mazui_len = len(mazui)

acc_umai = [0 for _ in range(umai_len)]
acc_umai[0] = umai[0][1]
for i in range(umai_len - 1):
    acc_umai[i + 1] = acc_umai[i] + umai[i + 1][1]

acc_mazui = [0 for _ in range(mazui_len)]
acc_mazui[0] = mazui[0][1]
for i in range(mazui_len - 1):
    acc_mazui[i + 1] = acc_mazui[i] + mazui[i + 1][1]
acc_mazui.insert(0, 0)

ans = []
for i in range(1, K + 1):
    if umai_len < i or mazui_len < K - i:
        continue
    ans.append(acc_umai[i - 1] + acc_mazui[K - i] + i ** 2)
print(max(ans))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x: -x[1])
items = sorted(items, key=lambda x: -x[1])

ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2

ans2 = 0
i = 1
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    if v + cnt ** 2 - (cnt - 1) ** 2 < items[i][0]:
        ans2 += items[i][0]
        cnt += 1
    else:
        select2.add(k)
        ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()
ans2 += cnt ** 2

remain = K - cnt
sel = set()
i += 1
while remain != 0:
    t, d = items[i]
    if t not in sel:
        i += 1
        sel.add(t)

    else:
        ans2 += d
        sel.add(t)
        remain -= 1
        i += 1
print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x: -x[1])
items = sorted(items, key=lambda x: -x[1])

ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2

ans2 = 0
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    select2.add(k)
    ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()
ans2 += cnt ** 2

remain = K - cnt
i = 1
sel = set()
while remain != 0:
    t, d = items[i]
    if t not in sel:
        ans2 += d
        sel.add(t)
        remain -= 1
        i += 1
    else:
        i += 1
        sel.add(t)
print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x: -x[1])
items = sorted(items, key=lambda x: -x[1])

ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2

ans2 = 0
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    select2.add(k)
    ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()
ans2 += cnt ** 2
remain = K - cnt
i = 1
sel = set()
while remain != 0:
    t, d = items[i]
    if t not in sel:
        ans2 += d
        sel.add(t)
        remain -= 1
    else:
        i += 1
        sel.add(t)
print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x: -x[1])
items = sorted(items, key=lambda x: -x[1])

ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2

ans2 = 0
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    select2.add(k)
    ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()

remain = K - cnt
i = 1
sel = set()
while remain != 0:
    t, d = items[i]
    if t not in sel:
        ans2 += d
        sel.add(t)
        remain -= 1
    else:
        i += 1
        sel.add(t)
print(max(ans1, ans2))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
items = []
neta = {}
for _ in range(N):
    t, d = tuple(map(int, input().split()))
    items.append((t, d))

    if t not in neta:
        neta[t] = d
    else:
        tmp = neta[t]
        if d > tmp:
            neta[t] = d

neta = sorted(neta.items(), key=lambda x:-x[1])
items = sorted(items, key=lambda x: -x[1])


ans1 = 0
select1 = set()
for i in range(K):
    t, d = items[i]
    select1.add(t)
    ans1 += d
ans1 += len(select1) ** 2


ans2 = 0
select2 = set()
cnt = 0
for k, v in neta:
    cnt += 1
    select2.add(k)
    ans2 += v
    if cnt == K:
        ans2 += cnt ** 2
        print(max(ans1, ans2))
        exit()

remain = K - cnt
i = 1
sel = set()
while remain != 0:
    t, d = items[i]
    if t not in sel:
        ans2 += d
        sel.add(t)
    else:
        i += 1
        sel.add(t)
print(max(ans1, ans2))