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: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
td=[list(map(int,input().split())) for i in range(N)]
best=[0]*(N+1)
other=[]
from heapq import heappop,heappush
td.sort(key=lambda x: x[1],reverse=True)
shurui=0
for i in range(K):
    if best[td[i][0]]==0:
        best[td[i][0]]=td[i][1]
        shurui+=1
    elif best[td[i][0]]<td[i][1]:
        heappush(other,best[td[i][0]])
        best[td[i][0]]=td[i][1]
    else:
        heappush(other,td[i][1])

ans=sum(best)+sum(other)+shurui**2

for i in range(K,N):
    if best[td[i][0]]==0 and len(other)>0:
        best[td[i][0]]=td[i][1]
        shurui+=1
        heappop(other)
        ans=max(ans,sum(best)+sum(other)+shurui**2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N, K = map(int, input().split())

table = [[] for _ in [0] * N]

for _ in [0]*N:
    t, d = map(int, input().split())
    table[t - 1].append(d)

table = [sorted(t,reverse=True) for t in table]

ones = sorted([table[i][0] for i in range(N) if len(table[i]) > 0], reverse=True)
zeros = sorted([table[i][j] for i in range(N) for j in range(1, len(table[i])) if len(table[i]) > 0], reverse=True)

ans = 0
for y in range(1, K + 1):
    if y > len(ones):
        break
    if y + len(zeros) < K:
        continue
    tmp = y * y + sum(ones[:y]) + sum(zeros[:K - y])
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
td=[]
for i in range(N):
    t,d=map(int,input().split())
    td.append([t,d])
td.sort(key=lambda x:x[1],reverse=True)
A=td[:K]
B=[]
s2=set()
for i,j in td[K:]:
    if not(i in s2):
        s2.add(i)
        B.append([i,j])
s1=set()
n=0
C=[]
sum=0
for i,j in A:
    if not(i in s1):
        s1.add(i)
        n+=1
        sum+=j
    else:
        C.append([i,j])
        sum+=j
sum+=n**2
B.reverse()
D=[]
for i,j in B:
    if not(i in s1):
        D.append([i,j])
list=[sum]
while(C):
    if D:
        i,j=D.pop()
        list.append(list[-1]+2*n+1+(j-C[-1][1]))
        n+=1
        C.pop()
print(max(list))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import Counter
import heapq

N, K = [int(v) for v in input().split()]
sushi = [tuple(int(v) for v in input().split()) for i in range(N)]

sushi = sorted(sushi, key=itemgetter(1), reverse=True)

ate_list = sushi[:K]

kind_counter = Counter([s[0] for s in ate_list])
kind_cnt = len(list(kind_counter))

kind_cnt_seq = kind_cnt ** 2
max_pt = sum([s[1] for s in ate_list]) + kind_cnt_seq

if K >= N:
    print(max_pt)
    exit()

# print(ate_list)

waiting_sushi = []
wait_kind = []
for s in sushi[K:]:
    if kind_counter[s[0]]:  # すでに食べてる種類
        continue

    if not s[0] in wait_kind:
        waiting_sushi.append(s)
        wait_kind.append(s[0])

# 食べた種類を増やしていくフェーズ
idx = K - 1

# print(waiting_sushi)

curr_pt = max_pt
for s in waiting_sushi:
    target = None
    for i in range(idx, -1, -1):
        # 1個しかないものは交換しない
        if kind_counter[ate_list[i][0]] > 1:
            target = ate_list[i]
            idx = i
            break

    if not target:
        break

    # 入れ替えして比較
    n_kind_cnt_seq = ((kind_cnt + 1) ** 2)
    curr_pt = curr_pt - target[1] + s[1] + n_kind_cnt_seq - kind_cnt_seq
    kind_cnt_seq = n_kind_cnt_seq

    max_pt = max(curr_pt, max_pt)
    kind_counter[target[0]] -= 1

    kind_cnt += 1
    idx -= 1

# print(kind_cnt)
print(max_pt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import Counter
import heapq

N, K = [int(v) for v in input().split()]
sushi = [tuple(int(v) for v in input().split()) for i in range(N)]

sushi = sorted(sushi, key=itemgetter(1), reverse=True)

ate_list = sushi[:K]

kind_counter = Counter([s[0] for s in ate_list])
kind_cnt = len(list(kind_counter))

max_pt = sum([s[1] for s in ate_list]) + kind_cnt ** 2

if K >= N:
    print(max_pt)
    exit()

# print(ate_list)

waiting_sushi = []
wait_kind = []
for s in sushi[K:]:
    if kind_counter[s[0]]:  # すでに食べてる種類
        continue

    if not s[0] in wait_kind:
        waiting_sushi.append(s)
        wait_kind.append(s[0])

# 食べた種類を増やしていくフェーズ
idx = K - 1

# print(waiting_sushi)

curr_pt = max_pt
for s in waiting_sushi:
    target = None
    for i in range(idx, -1, -1):
        # 1個しかないものは交換しない
        if kind_counter[ate_list[i][0]] > 1:
            target = ate_list[i]
            idx = i
            break

    if not target:
        break

    # 入れ替えして比較
    val = curr_pt - target[1] + s[1] + ((kind_cnt + 1) ** 2) - (kind_cnt ** 2)
    curr_pt = val

    max_pt = max(curr_pt, max_pt)
    kind_counter[target[0]] -= 1

    kind_cnt += 1
    idx -= 1

# print(kind_cnt)
print(max_pt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

table = [[] for _ in [0]*N]


for _ in range(N):
    t, d = map(int, input().split())
    table[t-1].append(d)

for i in range(N):
    table[i] = sorted(table[i],reverse=True)


ones = sorted([table[i][0] for i in range(N) if len(table[i])>0], reverse=True)
zeros = sorted([table[i][j] for i in range(N) for j in range(1,len(table[i])) if len(table[i]) > 0],reverse=True)


ans = 0
for y in range(1,K+1):
    if y > len(ones):
        break
    if y + len(zeros) < K:
        continue
    tmp = y*y + sum(ones[:y])+sum(zeros[:K-y])
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

table = [[] for _ in [0]*N]


for _ in range(N):
    t, d = map(int, input().split())
    table[t-1].append(d)

for i in range(N):
    table[i] = sorted(table[i],reverse=True)


ones = sorted([table[i][0] for i in range(N) if len(table[i])>0], reverse=True)
zeros = sorted([table[i][j] for i in range(N) for j in range(1,len(table[i])) if len(table[i]) > 0],reverse=True)


ans = 0
for y in range(1,K+1):
    if y > len(ones):
        break
    if y + len(zeros) < K:
        continue
    #print(ones[:y],zeros[:K-y])
    tmp = (y)**2 + sum(ones[:y]+zeros[:K-y])
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())

table = {(i+1):[] for i in range(N)}

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

for k in table:
    table[k] = sorted(table[k],reverse=True)

ones = sorted([table[k][0] for k in table if len(table[k])>0],reverse=True)
zeros = sorted([table[k][i] for k in table for i in range(1,len(table[k])) if len(table[k]) > 0],reverse=True)

ans = 0

for y in range(1,K+1):
    if y > len(ones):
        break
    if y + len(zeros) < K:
        continue
    tmp = (y)**2 + sum(ones[:y]+zeros[:K-y])
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

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

table = {(i+1):[] for i in range(N)}

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

for k in table:
    table[k] = sorted(table[k],reverse=True)

ones = sorted([table[k][0] for k in table if len(table[k])>0],reverse=True)
zeros = sorted([table[k][i] for k in table for i in range(1,len(table[k])) if len(table[k]) > 0],reverse=True)

ans = 0

for y in range(1,K+1):
    if y > len(ones):
        break
    if y + len(zeros) < K:
        continue
    tmp = (y)**2 + sum(ones[:y]+zeros[:K-y])
    ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
import collections

# 集合の中の種類数を出す


def v(l):
    t = set([])
    for i in range(len(l)):
        t.add(l[i][2])
    return len(t)


def calcNext(base, netas, types, index):
    removeTarget = 0
    for i in range(1, len(base) + 1):
        t = base[-i][2]
        if types[t] > 1:
            removeTarget = len(base)-i
            types[t] -= 1
            break
    next = []
    for i in range(len(base)):
        if i == removeTarget:
            continue
        next.append(base[i])
    nextIndex = index
    for i in range(index, len(netas)):
        nextIndex = i
        if types[netas[i][2]] == 0:
            next.append(netas[i])
            types[netas[i][2]] = 1
            break
    return (next, nextIndex)


def score(l):
    sum = 0
    for i in l:
        sum += i[1]
    va = v(l)
    sum += va*va
    return sum


def solve(N: int, K: int, t: "List[int]", d: "List[int]"):
    netas = [(-d[i], d[i], t[i]) for i in range(N)]
    netas.sort()
    maxT = v(netas)
    S = []
    C = [[] for i in range(maxT+1)]
    T = collections.defaultdict(int)
    for i in range(K):
        S.append(netas[i])
        T[netas[i][2]] += 1
    a = v(S)
    C[a] = S
    index = K
    for t in range(a+1, maxT+1):
        C[t], index = calcNext(C[t-1], netas, T, index)
    scores = [score(c) for c in C]
    print(max(scores))
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    t = [int()] * (N)  # type: "List[int]"
    d = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        t[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, K, t, d)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	man = 0
	syu = 0
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
		if i < K:
			man += d
			if t == 1:
				syu += 1
	
	ans = man + (syu ** 2)
	tmp1 = sorted(osushi_list, key = lambda k:k[1], reverse=True)
	tmp2 = sorted(osushi_list, key = lambda k:k[1])
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		for i, val in enumerate(tmp1):
			d, t = val
			syu_local += 1
			man += d
			count += 1
			if syu_local == syu_mokuhyou or count >= K:
				break
					
		for i, val in enumerate(tmp2):
			if count >= K:
				break
			d, t = val
			man += d
			count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	man = 0
	syu = 0
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
		if i < K:
			man += d
			if t == 1:
				syu += 1
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		tmp = sorted(osushi_list, key = lambda k:k[1], reverse=True)
		for i, val in enumerate(tmp):
			d, t = val
			syu_local += 1
			man += d
			count += 1
			if syu_local == syu_mokuhyou or count >= K:
				break
					
		tmp = sorted(osushi_list, key = lambda k:k[1])
		for i, val in enumerate(tmp):
			if count >= K:
				break
			d, t = val
			man += d
			count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	man = 0
	syu = 0
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
		if i < K:
			man += d
			if t == 1:
				syu += 1
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		for i, val in enumerate(osushi_list):
			d, t = val
			if t == 1:
				syu_local += 1
				man += d
				count += 1
				if syu_local == syu_mokuhyou or count >= K:
					break
					
		for i, val in enumerate(osushi_list):
			if count >= K:
				break
			d, t = val
			if t == 0:
				man += d
				count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_right

def main():
	N, K = map(int, input().split(" "))
	osushi = []
	for _ in  range(N):
		t, d = map(int, input().split(" "))
		osushi.append((d, t))
		
	osushi.sort()
	osushi.reverse()
	
	osushi_list = []
	syu_total = 0
	syu_list = []
	for i, val in enumerate(osushi):
		d, t = val;
		if not t in syu_list:
			syu_total += 1
			syu_list.append(t)
			t = 1
		else:
			t = 0
		osushi_list.append((d, t))
	
	man = 0
	syu = 0
	for i, val in enumerate(osushi_list):
		if i >= K:
			break
		d, t = val
		if t == 1:
			syu += 1
		man += d
	
	ans = man + (syu ** 2)
	for syu_mokuhyou in range(syu+1, syu_total+1):
		man = 0
		syu_local = 0
		count = 0
		for i, val in enumerate(osushi_list):
			d, t = val
			if t == 1:
				syu_local += 1
				man += d
				count += 1
				if syu_local == syu_mokuhyou or count >= K:
					break
					
		for i, val in enumerate(osushi_list):
			if count >= K:
				break
			d, t = val
			if t == 0:
				man += d
				count += 1
		tmp = man + (syu_local ** 2)
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
sn, tn, *s = map(int, open(0).read().split())
sy_oi = [[s[i * 2], s[i * 2 + 1]] for i in range(sn)]
sy_oi.sort(key=lambda x: -x[1])
cho = sy_oi[tn - 1::-1]
zan = sy_oi[tn:]
zn = sn - tn
# チョイスした種類の辞書
sydic = {}
for x in cho:
    if x[0] in sydic:
        sydic[x[0]] += 1
    else:
        sydic[x[0]] = 1
ot = sum([x[1] for x in cho])  # おいしさポイント
mt = len(sydic)  # まんぞくポイント
ans = ot + mt ** 2
zi = 0
cnt = 0
while 1:
    # チョイスから削除できるものを探す
    for i in range(tn - cnt):
        if sydic[cho[i][0]] > 1:
            sydic[cho[i][0]] -= 1
            ot -= cho[i][1]
            del cho[i]
            break
    else:
        break
    # 残から加えるものを探す
    for i in range(zi, zn):
        if zan[i][0] not in sydic:
            sydic[zan[i][0]] = 1
            ot += zan[i][1]
            mt += 1
            zi = i
            break
    else:
        break
    # 得点計算して更新
    ans = max(ans, ot + mt ** 2)
    cnt += 1
print(ans)

Submission status: Time Limit Exceeded

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

TD = sorted(TD, key=lambda x: x[1], reverse=True)

X = []
Y = []  # 一番美味しい寿司
kind = set()
for i in range(N):
    t, d = TD[i]
    if t in kind:
        X.append(d)
    else:
        Y.append(d)
        kind.add(t)

L = len(Y)
ans, rans = 0, 0
for i in range(1, K+1):
    if len(X) < K - i or len(Y) < i:
        continue
    ans = sum(Y[0:i]) + (i**2) + sum(X[0:K - i])
    rans = max(rans, ans)
print(rans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, K =  map(int, (input().split(' ')))
sushi = [tuple(map(int, input().split(' '))) for _ in range(N)]
all_sushi = sorted(sushi, key=lambda x: -x[1])
default_sushi = all_sushi[:K]
amari = all_sushi[K:]
counter = Counter([i[0] for i in default_sushi])
result = []
def calc_value(sushi):
    return sum([i[1] for i in sushi]) + len(counter)**2

fs = []
def change_sushi(sushi):
    oishisa = sum([i[1] for i in sushi])
    fs.append(oishisa + len(counter)**2)
    amari_index = 0
    for s in sushi[::-1]:
        if counter[s[0]] >= 2:
            for i, a in enumerate(amari[amari_index:], start=1):
                if a[0] not in counter:
                    counter[s[0]] -= 1
                    counter[a[0]] += 1
                    oishisa = oishisa - s[1] + a[1]
                    #amari = amari[:i] + amari[i+1:]
                    #sushi = [a] + sushi[:-1]
                    #return sushi
                    fs.append(oishisa + len(counter)**2)
                    amari_index = amari_index + i
                    
                    break
    print(max(fs))
    exit()
            
    
def get_sushi(sushi):
    #result.append(calc_value(sushi))
    changed_sushi = change_sushi(sushi)
    #if not changed_sushi:
        #print(max(result))
        #return
    #get_sushi(changed_sushi)

get_sushi(default_sushi)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, K =  map(int, (input().split(' ')))
sushi = [tuple(map(int, input().split(' '))) for _ in range(N)]
all_sushi = sorted(sushi, key=lambda x: -x[1])
default_sushi = all_sushi[:K]
amari = all_sushi[K:]
counter = Counter([i[0] for i in default_sushi])
result = []
def calc_value(sushi):
    return sum([i[1] for i in sushi]) + len(counter)**2

fs = []
def change_sushi(sushi):
    oishisa = sum([i[1] for i in sushi])
    fs.append(oishisa + len(counter)**2)
    for s in sushi[::-1]:
        if counter[s[0]] >= 2:
            for i, a in enumerate(amari):
                if a[0] not in counter:
                    counter[s[0]] -= 1
                    counter[a[0]] += 1
                    oishisa = oishisa - s[1] + a[1]
                    #amari = amari[:i] + amari[i+1:]
                    #sushi = [a] + sushi[:-1]
                    #return sushi
                    fs.append(oishisa + len(counter)**2)
    print(max(fs))
    exit()
            
    
def get_sushi(sushi):
    #result.append(calc_value(sushi))
    changed_sushi = change_sushi(sushi)
    #if not changed_sushi:
        #print(max(result))
        #return
    #get_sushi(changed_sushi)

get_sushi(default_sushi)

Submission status: Time Limit Exceeded

Solution code:
import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    index = 0
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val,index

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2,index = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    sushi_list = sushi_list[index:]
    if not sushi_list:
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Submission status: Time Limit Exceeded

Solution code:
import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku
flg = 0
while double_sushi:
    if(flg == 0):
        tmp1 = double_sushi.pop()
        max_val = [0,0]
        for i in range(len(sushi_list)):
            if(sushi_list[i][1] not in eaten_sushi):
                tmp = sushi_list[i]
                max_val = sushi_list[i]
                break
            flg = 1
    tmp2 = max_val
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Submission status: Time Limit Exceeded

Solution code:
import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Submission status: Time Limit Exceeded

Solution code:
import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
ans = []
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
        ans.append(sushi_list[i])
    else:
        ans.append(sushi_list[i])
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(ans)):
    manzoku += ans[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys

n,k = map(int, input().split())
td = []
td_mx = {}
for _ in range(n):
  t,d = map(int, input().split())
  td.append(d)
  if (t not in td_mx) or (td_mx[t] < d):
    td_mx[t] = d
td = sorted(td)
td_mx = sorted(td_mx.values())

mx_sum = 0
t_mx = len(td_mx)
ans = 0
for t in range(1, min(t_mx,k)+1):
  mx_sum += td_mx[-1]
  td.remove(td_mx[-1])
  td_mx.pop(-1)
  if t < k:
    ans = max(ans, mx_sum + sum(td[-k+t:]) + t**2)
  else:
    ans = max(ans, mx_sum + t**2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
t,d = list(zip(*sorted([list(map(int,input().split())) for _ in range(N) ],key=lambda x: (-x[1],x[0]))))

def get_value(sushi):
    ret = 0
    var = set()
    for i in sushi:
        ret += d[i]
        var.add(t[i])
    l = len(var)
    return ret + l*l

sushi = set()
sushi = set([(i,sushi.add(i))[0] for i in range(N) if t[i] not in [t[j] for j in sushi]][:K])
sushi |= set(list(set(range(N))-sushi)[:K-len(sushi)])

while 1:
    tmp = sushi - {max(sushi)}
    tmp.add(min(set(range(N)) - tmp))
    if get_value(tmp) <= get_value(sushi):
        break
    else:
        sushi = tmp
print(get_value(sushi))

Submission status: Time Limit Exceeded

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

def point(x):
    oishisa = sum(d[i] for i in x)
    nt = len(set(t[i] for i in x))
    return oishisa + nt * nt
    
from itertools import combinations
bp = -1
for x in combinations(range(n), k):
    bp = max(bp, point(x))
print(bp)

Submission status: Time Limit Exceeded

Solution code:
import sys

N, K = map(int,sys.stdin.readline().rstrip().split())
T = {}
for i in range(N):
    t, d = map(int,sys.stdin.readline().rstrip().split())
    if t not in T.keys():
        T[t] = []
    T[t].append(d)

for t in T.keys():
    T[t] = sorted(T[t], reverse=True)

T1 = []
T2 = []
for t in T.keys():
    T1.append(T[t][0])
    T2 += T[t][1:]

T1 = sorted(T1, reverse=True)
T2 = sorted(T2, reverse=True)
max_sc = 0
max_t = min(len(T1), K)
min_t = max(1, K - len(T2))
sc_d = 0
for i in range(min_t, max_t + 1):
    if i == min_t:
        sc_d = sum(T1[:i]) + sum(T2[:K - i])
    else:
        sc_d += T1[i - 1] - T2[K - i]
    sc = sc_d + i * i
    max_sc = max(max_sc, sc)

print(max_sc)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
T = {}
for i in range(N):
    t, d = map(int, input().split())
    if t not in T.keys():
        T[t] = []
    T[t].append(d)

for t in T.keys():
    T[t] = sorted(T[t], reverse=True)

T1 = []
T2 = []
for t in T.keys():
    T1.append(T[t][0])
    T2 += T[t][1:]

T1 = sorted(T1, reverse=True)
T2 = sorted(T2, reverse=True)
max_sc = 0
max_t = min(len(T1), K)
min_t = max(1, K - len(T2))
sc_d = 0
for i in range(min_t, max_t + 1):
    if i == min_t:
        sc_d = sum(T1[:i]) + sum(T2[:K - i])
    else:
        sc_d += T1[i - 1] - T2[K - i]
    sc = sc_d + i * i
    max_sc = max(max_sc, sc)

print(max_sc)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


sushi.sort(key=lambda x: x[1], reverse=True)

def find_next(start, curr, point, tlist, tcount):
    if start == N:
        return [point, curr]
    max_c = curr
    max_p = point
    for s in sushi[start:]:
        if tlist[s[0]] > 0:
            continue
        for ri in range(len(curr) - 1, -1, -1):
            r = curr[ri]
            if tlist[r[0]] >= 2:
                c2 = [c for c in curr]
                t2 = [t for t in tlist]
                del c2[ri]
                c2.append(s)
                t2[r[0]] -= 1
                t2[s[0]] = 1
                p2 = point - r[1] + s[1] + (tcount + 1) * (tcount + 1) - tcount * tcount
                np, pc = find_next(start + 1, c2, p2, t2, tcount + 1)

                if np > max_p:
                    max_p = np
                    max_c = pc
                return [max_p, max_c]
    return [max_p, max_c]

result = sushi[0: K]
type_count = [0] * (N + 1)

for r in result:
    type_count[r[0]] += 1
type_num = 0
for t in type_count:
    if t > 0:
        type_num += 1
point = type_num * type_num
for r in result:
    point += r[1]
ans_p, ans_c = find_next(K, result, point, type_count, type_num)

print(ans_p)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
sushi = []
for i in range(N):
    s = list(map(int, input().split()))
    sushi.append(s)


sushi.sort(key=lambda x: x[1], reverse=True)

def find_next(start, curr, point, tlist, tcount):
    if start == N:
        return [point, curr]
    max_c = curr
    max_p = point
    for s in sushi[start:]:
        if tlist[s[0]] > 0:
            continue
        for ri in range(len(curr) - 1, -1, -1):
            r = curr[ri]
            if tlist[r[0]] >= 2:
                c2 = [c for c in curr]
                t2 = [t for t in tlist]
                del c2[ri]
                c2.append(s)
                t2[r[0]] -= 1
                t2[s[0]] = 1
                p2 = point - r[1] + s[1] + (tcount + 1) * (tcount + 1) - tcount * tcount
                np, pc = find_next(start + 1, c2, p2, t2, tcount + 1)

                if np > max_p:
                    max_p = np
                    max_c = pc
                break
    return [max_p, max_c]

result = sushi[0: K]
type_count = [0] * (N + 1)

for r in result:
    type_count[r[0]] += 1
type_num = 0
for t in type_count:
    if t > 0:
        type_num += 1
point = type_num * type_num
for r in result:
    point += r[1]
ans_p, ans_c = find_next(K, result, point, type_count, type_num)

print(ans_p)