Problem:


Score : 400 points

Problem Statement

There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i.
You are choosing K among these N pieces to eat.
Your "satisfaction" here will be calculated as follows:

The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".

The base total deliciousness is the sum of the deliciousness of the pieces you eat.

The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.

You want to have as much satisfaction as possible.
Find this maximum satisfaction.

Constraints

1 \leq K \leq N  \leq 10^5

1 \leq t_i \leq N

1 \leq d_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

Output

Print the maximum satisfaction that you can obtain.

Sample Input 1

5 3
1 9
1 7
2 6
2 5
3 1

Sample Output 1

26

If you eat Sushi 1,2 and 3:

The base total deliciousness is 9+7+6=22.

The variety bonus is 2*2=4.

Thus, your satisfaction will be 26, which is optimal.

Sample Input 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Sample Output 2

25

It is optimal to eat Sushi 1,2,3 and 4.

Sample Input 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

Sample Output 3

4900000016

Note that the output may not fit into a 32-bit integer type.



Sample input:
5 3
1 9
1 7
2 6
2 5
3 1


Sample output:
26

Submission status: Wrong Answer

Solution code:
import math
import itertools

N,K = map(int, input().split())

dt = []
neta = []
bass_score = 0

for _ in range(N):
    tmp1,tmp2 = map(int, input().split())
    dt.append([tmp2,tmp1])


DT = dt.copy()
DT.sort(reverse=True)

for i in range(K):
    bass_score += DT[i][0]
    neta.append(DT[i][1])

bonus_score = len(set(neta))**2
test1 = bass_score + bonus_score
print(test1)
#----------------------------

# neta = []
# bass_score = 0
# count = 0
# for i in range(10**10):
#     if DT[i][1] in neta:
#         continue
#     else:
#         bass_score += DT[i][0]
#         neta.append(DT[i][1])
#         count += 1
#         if count == K:
#             break

# bonus_score = len(set(neta))**2
# test2 = bass_score + bonus_score

# print(max(test1,test2))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = []

for _ in range(N):
    t, d = map(int, input().split())
    a.append((d, t))

a.sort(key=lambda x: x[0], reverse=True)
# おいしさ降順

ans = 0
kk = 0
bl = [False for _ in range(N + 1)]
taken = []
taken2 = [False for _ in range(N)]
for i in range(N):
    d, t = a[i]
    if not bl[t]:
        ans += d
        kk += 1
        bl[t] = True
        taken.append(i)
        taken2[i] = True
    if kk == K:
        break
ans += kk * kk

# 各種類1個ずつ最大値を取った

if kk == K:
    # 入れ替え
    taken_idx = len(taken) - 1
    left = 0
    while True:
        to_rm_i = taken[taken_idx]

        flg = False

        b = 0
        b -= 2 * kk - 1
        b -= a[to_rm_i][0]
        for i in range(left, to_rm_i):
            if taken2[i]:
                pass
            else:
                d, t = a[i]
                x = b + d
                if x > 0:
                    ans += x
                    bl[t] = True
                    taken2[i] = True
                    kk -= 1
                    break
                else:
                    if not flg:
                        left = i
                        flg = True
        else:
            break
        taken_idx -= 1

else:
    ans -= kk * kk
    # 上から加算
    for i in range(N):
        if not taken2[i]:
            d, t = a[i]
            ans += d
            kk += 1
        if kk == K:
            break
    ans += kk * kk

print(ans)

Submission status: Wrong Answer

Solution code:

N,K = map(int,input().split())
td = []
td1 = [[] for _ in range(N+1)]
for i in range(N):
    t,d = map(int,input().split())
    td.append([t,d,0])
td = sorted(td,key = lambda x:x[1])[::-1]
ans = 0
s = set()
for i in range(K):
    ans += td[i][1]
    s.add(td[i][0])
ans += len(s)**2
ans1 = 0
n = set()
length = 0
count = 0
while(count < K):
    n = set()
    for i in range(len(td)):
        t,d,f = td[i]
        if f == 0:
            if t not in n and count < K:
                td[i][2] = 1
                n.add(t)
                ans1 += d
                count += 1
                continue
    length = max(length,len(n))
ans1 += length**2
print(max(ans,ans1))

Submission status: Wrong Answer

Solution code:
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 = 0
sel = set()

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))

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
sushi = [list(map(int,input().split())) for _ in range(N)]
point = 0
sushi_num = []
for t, d in sushi[:K]:
  point += d
  if(t not in sushi_num):
    sushi_num.append(t)
print(point + len(sushi_num)**2)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
sushi = []
for _ in range(N):
    t, d = map(int, input().split())
    sushi.append((d, t))

sushi = sorted(sushi, reverse=True)
pattern_A = sushi[:K]
score_A = sum([a[0] for a in pattern_A]) + len(set([a[1] for a in pattern_A]))**2
pattern_B = []
var = []
for s in sushi:
    if len(var) == K:
        break
    if s[1] not in var:
        pattern_B.append(s)
        var.append(s[1])
score_B = sum([b[0] for b in pattern_B]) + K**2
print(max(score_A, score_B))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, k = map(int, input().split())
td = sorted([list(map(int, input().split())) for i in range(n)], key=itemgetter(1), reverse=True)
BP = set()
MP = 0
syurui = set()
for i in range(n):
    syurui.add(td[i][0])
syurui_n = len(syurui)
max_syurui = min(k, syurui_n)
count = 0
for i in range(n):
    t, d = td[i]
    if td[i][0] in BP:
        if max_syurui ** 2 - (max_syurui - 1) ** 2 <= d:
            MP += d
            count += 1
    else:
        BP.add(t)
        MP += d
        count += 1
    if count == k:
        break
print(MP + len(BP) ** 2)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]

now = data[:K]


def count(x):
    p = len(set([a[0] for a in x]))
    point = p ** 2
    p = sum([a[1] for a in x])
    point += p
    return point

p_max = count(now)

for i in range(K, N):
    for j in range(K):
        c = now[:j] + now[j+1:]
        c + data[i]
        if count(c) > p_max:
            p_max = count(c)

print(p_max)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
sushi = []

for k in range(N):
    sushi.append(list(map(int,input().split())))

sushi = sorted(sushi, key=lambda x: -x[1])


t = 0
n = set()
for k in range(K):
    t += sushi[k][1]
    n.add(sushi[k][0])
ans = t + len(n)**2

for k in range(K,N):
    t -= sushi[2*K-k-1][1]
    t += sushi[k][1]
    n.add(sushi[k][0])
    ans = max(ans,t+len(n)**2)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict

N, K = [int(elem) for elem in fin().split()]
sushi_info = sorted(tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N)), key=lambda x: -x[1])

cur_eaten = []
cur_rest = []
count = defaultdict(int)
for t, d in sushi_info[:K]:
    heappush(cur_eaten, (d, t))
    count[t] += 1
for t, d in sushi_info[K:]:
    heappush(cur_rest, (-d, t))

num_distinctive_kinds = sum(v >= 1 for v in count.values())
satisfactions = [sum(d for _, d in sushi_info[:K]) + num_distinctive_kinds**2]

cur_num_kinds = num_distinctive_kinds
for _ in range(K - num_distinctive_kinds):
    while cur_eaten and count[cur_eaten[0][1]] <= 1:
        heappop(cur_eaten)
    while cur_rest and count[cur_rest[0][1]] > 0:
        heappop(cur_rest)
    if (not cur_eaten) or (not cur_rest):
        break
    ditched_d, ditched_t = heappop(cur_eaten)
    added_d, added_t = heappop(cur_rest)
    added_d *= -1
    count[ditched_t] -= 1
    count[added_d] += 1
    cur_num_kinds += 1
    satisfactions.append(satisfactions[-1] - ditched_d + added_d + cur_num_kinds*2 - 1)

# print(satisfactions)
print(max(satisfactions))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = []

for _ in range(N):
    t, d = map(int, input().split())
    a.append((d, t))

a.sort(key=lambda x: x[0], reverse=True)
# おいしさ降順

ans = 0
kk = 0
bl = [False for _ in range(N + 1)]
taken = []
taken2 = [False for _ in range(N)]
for i in range(N):
    d, t = a[i]
    if not bl[t]:
        ans += d
        kk += 1
        bl[t] = True
        taken.append(i)
        taken2[i] = True
    if kk == K:
        break
ans += kk * kk

# 各種類1個ずつ最大値を取った

if kk == K:
    # 入れ替え
    taken_idx = len(taken) - 1

    while True:
        to_rm_i = taken[taken_idx]

        b = 0
        b -= 2 * kk - 1
        b -= a[to_rm_i][0]
        for i in range(to_rm_i):
            if not taken2[i]:
                d, t = a[i]
                if b + d > 0:
                    ans += b
                    ans += d
                    bl[t] = True
                    taken.append(i)
                    taken2[i] = True
                    kk -= 1
                break
        else:
            break
        taken_idx -= 1

else:
    ans -= kk * kk
    # 上から加算
    for i in range(N):
        if not taken2[i]:
            d, t = a[i]
            ans += d
            kk += 1
            bl[t] = True
            taken.append(i)
            taken2[i] = True
        if kk == K:
            break
    ans += kk * kk

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
td = []
for _ in range(n):
    tdi = list(map(int, input().split()))
    td.append(tdi)

sorted(td, key=lambda x: -x[1])

# ネタで攻める
oisisa = 0
shurui = []
max1 = 0
i = 0
for temp in td:
    if i == k:
        break
    oisisa += temp[1]
    shurui.append(temp[0])
    i += 1

max1 = len(set(shurui))**2 + oisisa
# print(max1)

# 種類で攻める
oisisa = 0
shurui = []
max2 = 0
i = 0
for temp in td:
    if i == k:
        break
    if temp[0] in shurui:
        continue
    oisisa += temp[1]
    shurui.append(temp[0])
    i += 1

max2 = len(set(shurui))**2 + oisisa

# 比較
max = max1 if max1 > max2 else max2
print(max)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
t=[[] for i in range(N)]
for i in range(N):
    a,b=map(int,input().split())
    t[i].append(a)
    t[i].append(b)
t.sort(key=lambda x:x[1],reverse=True)
x=0
y=0
var=[]
var.append(t[0][0])
d=1
for i in range(K):
    x+=t[i][1]
    for h in var:
        if t[i][0]==h:
            d=0
            break
    if d==1:
        var.append(t[i][0])
    d=1
t.sort(key=lambda x:(x[0],x[1]),reverse=True)
s=t[0][0]
y+=t[0][1]
c=1
for i in range(1,N):
    if t[i][0]!=s:
        s=t[i][0]
        y+=t[i][1]
        c+=1
    if c==K:
        break
print(max(x+len(var)*len(var),y+K*K))

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
t,d = [],[]
res_tup = []
for i in range(n):
    tmp = list(int(i) for i in input().split())
    t.append(tmp[0])
    d.append(tmp[1])
    res_tup.append((tmp[1],tmp[0]))

res_tup = sorted(res_tup,reverse = True)
res = 0
types = []
for i in range(k):
    res += res_tup[i][0]
    if not res_tup[i][1] in types:
        types.append(res_tup[i][1])
res += len(types)*len(types)

tmp = 0
types = []
used =[]
for i in range(n):
    if not res_tup[i][1] in types:
        tmp += res_tup[i][0]
        types.append(res_tup[i][1])
        used.append(i)
    if len(types)==k:
        break
if not len(types)==k:
    for i in range(n):
        if not i in used:
            tmp += res_tup[i][0]
            types.append(res_tup[i][1])
        if len(types)==k:
            break
tmp += k*k
res = max(res,tmp)
print(res)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())

M = [[None for k in range(K+1)] for n in range(N+1)]
T = [[None for k in range(K+1)] for n in range(N+1)]
D = [[None for k in range(K+1)] for n in range(N+1)]

for n in range(N+1):
    if n > 0:
        t, d  = map(int, input().split())
    for k in range(K+1):
        if n == 0 or k == 0:
            M[n][k] = 0
            T[n][k] = []
            D[n][k] = 0
        elif k > n:
            M[n][k] = M[n-1][k-1]
            T[n][k] = T[n-1][k-1]
            D[n][k] = D[n-1][k-1]
        else:
            T_add = list(set(T[n-1][k-1] + [t]))
            D_add = D[n-1][k-1] +  d
            M_add = D_add + len(set(T_add)) ** 2
            if M_add > M[n-1][k]:
                M[n][k] = M_add
                T[n][k] = T_add
                D[n][k] = D_add
            elif M_add == M[n-1][k]:
                if len(T_add) < len(T[n-1][k]):
                    M[n][k] = M_add
                    T[n][k] = T_add
                    D[n][k] = D_add
                else:
                    M[n][k] = M[n-1][k]
                    T[n][k] = T[n-1][k]
                    D[n][k] = D[n-1][k]
            else:
                M[n][k] = M[n-1][k]
                T[n][k] = T[n-1][k]
                D[n][k] = D[n-1][k]

print(M[N][K])

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, k = map(int, input().split())
td = sorted([list(map(int, input().split())) for i in range(n)], key=itemgetter(1), reverse=True)
BP = set()
MP = 0
syurui = set()
for i in range(n):
    syurui.add(td[i][0])
syurui_n = len(syurui)
max_syurui = min(k, syurui_n)
count = 0
for i in range(n):
    t, d = td[i]
    if td[i][0] in BP:
        if max_syurui ** 2 - (max_syurui - 1) ** 2 < d:
            MP += d
            count += 1
    else:
        BP.add(t)
        MP += d
        count += 1
    if count == k:
        break
print(MP + len(BP) ** 2)

Submission status: Wrong Answer

Solution code:
ans = 0

def calc_final_data(suhsi_data, eat_data, sushi_num):
    global ans
    ans_kari = 0
    neta_hist = set()
    for i in range(sushi_num):
        if eat_data[i]:
            neta_hist.add(str(suhsi_data[i][0]))
            ans_kari += suhsi_data[i][1]
    ans_kari += len(neta_hist) * len(neta_hist)
    if ans_kari > ans:
        ans = ans_kari

def eat_sushi(suhsi_data, max_eat, eat_data_kari, index, eat_flg, sushi_num):
    eat_data = eat_data_kari.copy()
    if sushi_num - index < max_eat - eat_data.count(1):
        return
    if index == sushi_num or eat_data.count(1) == max_eat:
        calc_final_data(suhsi_data, eat_data, sushi_num)
        return
    if eat_flg:
        eat_data[index] = 1
    eat_sushi(suhsi_data, max_eat, eat_data, index+1, 0, sushi_num)
    eat_sushi(suhsi_data, max_eat, eat_data, index+1, 1, sushi_num)

def first_step(suhsi_data, max_eat, eat_data, sushi_num):
    sorted(suhsi_data, key=lambda x: -x[1])
    neta_shurui = set()
    for i in range(sushi_num):
        neta_shurui.add(str(suhsi_data[i][0]))
    eat_num = max_eat - len(neta_shurui)

    count = 0
    eat_shurui = set()
    for i in range(sushi_num):
        if count == eat_num:
            break
        eat_data[i] = 1
        if str(suhsi_data[i][0]) in eat_shurui:
            count += 1
        else:
            eat_shurui.add(str(suhsi_data[i][0]))


    return eat_data, suhsi_data


def calc_eat(suhsi_data, max_eat, eat_data, sushi_num):
    eat_data, suhsi_data = first_step(suhsi_data, max_eat, eat_data, sushi_num)
    eat_sushi(suhsi_data, max_eat, eat_data, eat_data.count(1), 0, sushi_num)
    eat_sushi(suhsi_data, max_eat, eat_data, eat_data.count(1), 1, sushi_num)

def print_ans():
    global ans
    print(ans)

def main():
    sushi_num, max_eat = list(map(int, input().split()))
    suhsi_data = [list(map(int, input().split())) for i in range(sushi_num)]
    eat_data = [0 for i in range(sushi_num)]
    calc_eat(suhsi_data, max_eat, eat_data, sushi_num)
    print_ans()

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())

M = [[None for k in range(K+1)] for n in range(N+1)]
T = [[None for k in range(K+1)] for n in range(N+1)]
D = [[None for k in range(K+1)] for n in range(N+1)]

for n in range(N+1):
    if n > 0:
        t, d  = map(int, input().split())
    for k in range(K+1):
        if n == 0 or k == 0:
            M[n][k] = 0
            T[n][k] = []
            D[n][k] = 0
        elif k > n:
            M[n][k] = M[n-1][k-1]
            T[n][k] = T[n-1][k-1]
            D[n][k] = D[n-1][k-1]
        else:
            T_add = list(set(T[n-1][k-1] + [t]))
            D_add = D[n-1][k-1] +  d
            M_add = D_add + len(set(T_add)) ** 2
            if M_add > M[n-1][k]:
                M[n][k] = M_add
                T[n][k] = T_add
                D[n][k] = D_add
            elif M_add == M[n-1][k]:
                if len(T_add) > len(T[n-1][k]):
                    M[n][k] = M_add
                    T[n][k] = T_add
                    D[n][k] = D_add
                else:
                    M[n][k] = M[n-1][k]
                    T[n][k] = T[n-1][k]
                    D[n][k] = D[n-1][k]
            else:
                M[n][k] = M[n-1][k]
                T[n][k] = T[n-1][k]
                D[n][k] = D[n-1][k]

print(M[N][K])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
tp = []
dp = []
Sp = 0
kinds = set([])
for i in range(n):
    t, d = map(int, input().split())
    tp.append(t)
    dp.append(d)


for i in range(k):
    index = dp.index(max(dp))
    Sp += max(dp)
    kinds.add(tp[index])
    tp.pop(index)
    dp.pop(index)

Sp += len(kinds) * len(kinds)
print(Sp)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
t,d = [],[]
res_tup = []
for i in range(n):
    tmp = list(int(i) for i in input().split())
    t.append(tmp[0])
    d.append(tmp[1])
    res_tup.append((tmp[1],tmp[0]))

res_tup = sorted(res_tup,reverse = True)
res = 0
types = []
for i in range(k):
    res += res_tup[i][0]
    if not res_tup[i][1] in types:
        types.append(res_tup[i][1])
res += len(types)*len(types)

tmp = 0
types = []
for i in range(n):
    if not res_tup[i][1] in types:
        tmp += res_tup[i][0]
        types.append(res_tup[i][1])
    if len(types)==k:
        break
tmp += k*k
res = max(res,tmp)
print(res)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def calc(sushis):
	manzoku_sushi = sum(list(map(lambda sushi: sushi[1], sushis[:k])))
	syurui = len(set(list(map(lambda sushi: sushi[0], sushis[:k]))))

	# print(sushis)
	# print(manzoku_sushi, syurui)
	return manzoku_sushi + syurui*syurui


n, k = map(int, input().split())
sushis = [tuple(map(int, input().split())) for _ in range(n)]

total_1 = calc( sorted(sushis, key=itemgetter(1,0), reverse=True) )
total_2 = calc( sorted(sushis, key=itemgetter(0,1), reverse=False) )


print(max(total_1, total_2))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
X = []
for i in range(N):
    t,d = map(int,input().split())
    X.append((d,t))

X.sort(reverse=True)

p,v = 0,set([])
pp = []
for i in range(K):
    p += X[i][0]
    if X[i][1] not in v:
        v.add(X[i][1])
    else:
        pp.append((X[i][0],X[i][1]))

Ans = p + len(v)**2
ans = Ans
for i in range(K,N):
    if X[i][1] not in v and len(pp)>0:
        ans = ans - pp[0][0] + X[i][0] - len(v)**2 + (len(v)+1)**2
        v.add(X[i][1])
        Ans = max(Ans,ans)
        pp = pp[1:]

print(Ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
sushi = [list(map(int,input().split())) for _ in range(N)]
sushi = sorted(sushi, key = lambda x:-x[1])
num_tmp = dict(sushi[:K])
if(len(num_tmp) <= int(K/2)):
  sushi = sorted(sushi, key = lambda x:(x[0],-x[1]))
point = 0
sushi_num = []
for i in range(K):
  t, d = sushi[i][0], sushi[i][1]
  point += d
  if(t not in sushi_num):
    sushi_num.append(t)
print(point + len(sushi_num)**2)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
dt = []
for i in range(N):
	t, d = map(int, input().split())
	dt.append((d, t))
dt.sort()
dt.reverse()
s = set([])
x = 0
for i in range(N):
	d, t = dt[i]
	if t not in s:
		s.add(t)
		x += 1
		dt[i] = (d + 2 * x - 1, t)
dt.sort()
dt.reverse()
ans = 0
for i in range(K):
	d, t = dt[i]
	ans += d
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())

M = [[None for k in range(K+1)] for n in range(N+1)]
T = [[None for k in range(K+1)] for n in range(N+1)]
D = [[None for k in range(K+1)] for n in range(N+1)]

for n in range(N+1):
    if n > 0:
        t, d  = map(int, input().split())
    for k in range(K+1):
        if n == 0 or k == 0:
            M[n][k] = 0
            T[n][k] = []
            D[n][k] = 0
        elif k > n:
            M[n][k] = M[n-1][k-1]
            T[n][k] = T[n-1][k-1]
            D[n][k] = D[n-1][k-1]
        else:
            T_add = list(set(T[n-1][k-1] + [t]))
            D_add = D[n-1][k-1] +  d
            M_add = D_add + len(set(T_add)) ** 2
            if M_add > M[n-1][k]:
                M[n][k] = M_add
                T[n][k] = T_add
                D[n][k] = D_add
            else:
                M[n][k] = M[n-1][k]
                T[n][k] = T[n-1][k]
                D[n][k] = D[n-1][k]

print(M[N][K])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append([i, x, y])

X = sorted(X, key = lambda x:x[2])[::-1]

p = 0
L = [0] * (N+1)
bonus = 0
for i in range(K):
    p += X[i][2]
    if L[X[i][1]] == 0:
        bonus += 1
        
    L[X[i][1]] += 1

p += bonus ** 2
ma = p
i = K-1
j = K
while True:
    while j < N and L[X[j][1]]:
        j += 1
    if j == N:
        break
    else:
        while i >= 0 and L[X[i][1]] <= 1:
            i -= 1
        if i < 0:
            break
        else:
            L[X[i][1]] -= 1
            L[X[j][1]] += 1
            p -= X[i][2]
            p += X[j][2]
            p += bonus * 2 + 1
            bonus += 1
            ma = max(ma, p)
            
    j += 1
        
print(ma)

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().split()]
td=[]
for _ in [0]*n:
    ti,di=[int(x) for x in input().split()]
    td.append((ti,di))
td=sorted(td,key=lambda x : x[1])
t=[x[0] for x in td]
d=[x[1] for x in td]
ans=0
for x in range(1,len(set(t))+1):
    tmpans=(x)**2
    tmpt,tmpd=t.copy(),d.copy()
    tmpk=k-x
    neta=set()
    i=0
    while len(neta)!=x:
        i-=1
        if tmpt[i] not in neta:
            neta.add(tmpt[i])
            tmpans+=tmpd[i]
            tmpt[i]=0
    for i in range(n):
        ti,di=tmpt[n-1-i],tmpd[n-1-i]
        if ti==0:
            continue
        if tmpk==0:
            break
        tmpk-=1
        tmpans+=di
    ans=max(ans,tmpans)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
a = []
for i in range(n):
    t,d = (int(num) for num in input().split())
    a.append([t,d])

def oishisa(list):
    return(list[1])

a.sort(key = oishisa, reverse = True)


ans = []

list_t = []
list_pos = [] #初めての新しい寿司
list_npos = []
for i in range(n):
    if a[i][0] not in list_t:
        list_t.append(a[i][0])
        list_pos.append(i)
    else:
        list_npos.append(i)


def score(a,l_takepos,shurui):
    s = shurui**2
    for num in l_takepos:
        s += a[num][1] #oishisa
    return s
        
minshurui = 0
for i in range(k):
    if i in list_pos:
        minshurui += 1
maxshurui = max(k,len(list_pos))

for j in range(minshurui,maxshurui+1,1):
    l_takepos = list_pos[:j]
    rest = k-j
    l_takepos += list_npos[:rest]
    ans.append(score(a,l_takepos,j))
    
print(max(ans))

Submission status: Wrong Answer

Solution code:
def calc(sushis):
	manzoku_sushi = sum(list(map(lambda sushi: sushi[1], sushis[:k])))
	syurui = len(set(list(map(lambda sushi: sushi[0], sushis[:k]))))

	# print(sushis)
	# print(manzoku_sushi, syurui)
	return manzoku_sushi + syurui*syurui


n, k = map(int, input().split())
sushis = [tuple(map(int, input().split())) for _ in range(n)]

total_1 = calc( sorted(sushis, key=lambda sushi: sushi[1], reverse=True) )
total_2 = calc( sorted(sushis, key=lambda sushi: sushi[0], reverse=False) )


print(max(total_1, total_2))

Submission status: Wrong Answer

Solution code:

n, k = list(map(int, input().split()))
td = {}
for _ in range(n):
    t, d = list(map(int, input().split()))
    if t in td:
        td[t].append(d)
    else:
        td[t] = [d]
for key in td.keys():
    td[key] = list(sorted(td[key]))
selected = {}
p = 0
x = 0
for _ in range(k):
    max_key = 0
    max_val = 0
    x = len(selected.keys())
    for key in td.keys():
        arr = td[key]
        if len(arr) == 0:
            continue
        m = arr[len(arr)-1]
        val = 0
        if key in selected:
            val = m
        else:
            val = m
            val += (x+1)*(x+1) - x*x
        if max_val < val:
            max_val = val
            max_key = key
    selected[max_key] = True
    p += max_val
    td[max_key].pop()
print(p)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

ans = 0

lo, hi = 0, K + 1
while abs(hi - lo) > 1:
    k = (lo + hi) // 2
    choice = 0
    variety = set()
    tmp = 0

    remain = max(0, K - k)

    for t, d in sushi:
        if t not in variety:
            tmp += d
            choice += 1
            variety.add(t)

        elif remain:
            tmp += d
            remain -= 1
            choice += 1

        if choice == K:
            break

    tmp += len(variety) ** 2

    if tmp < ans:
        hi = k
    else:
        lo = k
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for i in range(N)]
sushi.sort(key=lambda x: x[1], reverse=True)

ans = 0

lo, hi = 0, K + 1
while abs(hi - lo) > 1:
    k = (lo + hi) // 2
    choice = 0
    variety = set()
    tmp = 0

    remain = max(0, K - k)

    for t, d in sushi:
        if t not in variety:
            tmp += d
            choice += 1
            variety.add(t)

        elif remain:
            tmp += d
            remain -= 1
            choice += 1

        if choice == K:
            break

    tmp += len(variety) ** 2

    if tmp <= ans:
        hi = k
    else:
        lo = k
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append([i, x, y])

X = sorted(X, key = lambda x:x[2])[::-1]

p = 0
L = [0] * (N+1)
bonus = 0
for i in range(K):
    p += X[i][2]
    if L[X[i][1]] == 0:
        bonus += 1
        
    L[X[i][1]] += 1

p += bonus ** 2
ma = p
i = K-1
j = K
while True:
    while j < N and L[X[j][0]]:
        j += 1
    if j == N:
        break
    else:
        while i >= 0 and L[X[i][0]] <= 1:
            i -= 1
        if i < 0:
            break
        else:
            L[X[i][0]] -= 1
            L[X[j][0]] += 1
            p -= X[i][2]
            p += X[j][2]
            p += bonus * 2 + 1
            bonus += 1
            ma = max(ma, p)
            
    j += 1
    
print(ma)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
TD=[list(map(int,input().split())) for i in range(N)]
TD.sort(key=lambda x:x[1],reverse=True)

ANS=0

check=[0]*(10**5+1)
NOCHANGE=[]
NETA=[]

for i in range(K):
    ANS+=TD[i][1]
    NETA.append(TD[i][0])


for i in range(N):
    if check[TD[i][0]]==0:
        NOCHANGE.append(i)
        check[TD[i][0]]=1

NOCHANSET=set(NOCHANGE)
NETA=len(set(NETA))



NOWLIST=set(list(range(K)))
NOWLIST=sorted(list(NOWLIST-NOCHANSET))



NOCHANGE=sorted(list(NOCHANSET))

ANS+=NETA**2

#print(NOCHANGE)
#print(NOWLIST)
#print(ANS)
#print(NETA)

L=len(NOCHANGE)

for j in range(L):
    if NOCHANGE[j]>K-1:
        break

#print(j)
i=K-1

SCORE=ANS
while j<L:
    while i in NOCHANSET:
        i-=1

    if i<0:
        break


    SCORE+=TD[NOCHANGE[j]][1]-TD[i][1]-NETA**2+(NETA+1)**2
    if SCORE>ANS:
        ANS=SCORE
    #print(i,j,NETA,SCORE)
    NETA+=1
    j+=1
    i-=1


    #print(i,j)

print(ANS)

Submission status: Wrong Answer

Solution code:

n, k = list(map(int, input().split()))
td = {}
for _ in range(n):
    t, d = list(map(int, input().split()))
    if t in td:
        td[t].append(d)
    else:
        td[t] = [d]
for key in td.keys():
    td[key] = list((sorted(td[key])))
selected = {}
p = 0
x = 0
for _ in range(k):
    max_key = 0
    max_val = 0
    for key in td.keys():
        arr = td[key]
        if len(arr) == 0:
            continue
        m = arr[len(arr)-1]
        val = 0
        if key in selected:
            val = m
        else:
            val = m
            val += (x+1)*(x+1) - x*x
        if max_val < val:
            max_val = val
            max_key = key
    selected[max_key] = True
    p += max_val
    td[max_key].pop()
print(p)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
t=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    t[i],d[i]=map(int,input().split())
S=set()
ans=0
for i in range(K):
    S.add(t[i])
    ans+=d[i]
print(ans+len(S)**2)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())
a = []
for i in range(n):
    t,d = (int(num) for num in input().split())
    a.append([t,d])

def oishisa(list):
    return(list[1])

a.sort(key = oishisa, reverse = True)


ans = 0

list_t = []
list_pos = [] #初めての新しい寿司
list_npos = []
for i in range(n):
    if a[i][0] not in list_t:
        list_t.append(a[i][0])
        list_pos.append(i)
    else:
        list_npos.append(i)

s = 0
def score(a,l_takepos,shurui):
    s = shurui**2
    for num in l_takepos:
        s += a[num][1] #oishisa
    return s
        
minshurui = 0
for i in range(k):
    if i in list_pos:
        minshurui += 1
maxshurui = len(list_pos)       
for j in range(minshurui,maxshurui+1,1):
    l_takepos = list_pos[:j]
    rest = k-j
    l_takepos += list_npos[:rest]
    ans_sub = score(a,l_takepos,j)
    if ans_sub > ans:
        ans = ans_sub
print(ans)