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 = [int(x) for x in input().split()]

# sushi
s = {}
for i in range(N):
    t, d = [int(x) for x in input().split()]
    if not t in s:
        s[t] = [d]
    else:
        s[t].append(d)

# 各スシのMax
m = [max(v) for k, v in s.items()]
m.sort(reverse=True)

s2 = {}
all2 = []
for k in s.keys():
    s2[k] = sorted(s[k])
    s2[k].pop()
    all2 += s2[k]
all2.sort(reverse=True)

# スシ種類
# kinds = len(set([k for k in s.keys()]))
kinds = len(m)

ans = 0
for i in range(1, min(K, kinds) + 1):
    addM = m[:i]
    addAll2 = all2[:K - i]
    newAns = sum(addM) + sum(addAll2) + i ** 2
    ans = max(ans, newAns)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K= map(int,input().split())
n=0
lis=[]
points=0
kind=set()
l1=[]
l2=[]
for _ in range(N):
    t,d = map(int,input().split())
    lis.append((t,d))
lis.sort(key=lambda x:x[1],reverse=True)
for i in lis:
    if K>n:
        if i[0] not in kind:
            l1.append(i[1])
            kind.add(i[0])
        else:
            l2.append(i[1])
        n+=1
        if K==n:
            tl=sum(l1) +sum(l2) +len(kind)**2
            points=max(tl,points)
            if len(l2)==0:
                break
    else:
        if i[0] in kind:
            continue
        else:
            l2.pop(-1)
            l1.append(i[1])
            kind.add(i[0])
            tl=sum(l1) +sum(l2) +len(kind)**2
            points=max(tl,points)
            if len(l2)==0:
                break

print(points)

Submission status: Time Limit Exceeded

Solution code:
def score(l):
  return sum([i[1] for i in l])+len(set([i[0] for i in l]))**2

N,K=map(int, input().split())
L=[list(map(int, input().split())) for _ in range(N)]

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

L_kind=set([i[0] for i in L])
L_sorted_kind=set([i[0] for i in L_sorted[:K]])

bucket={k:len([k for i in L_sorted[:K] if i[0]==k]) for k in L_sorted_kind}

tmp=L_sorted[K:]
L_sorted_=[]
tmp_set=[]
for i in tmp:
  if not (i[0] in set(L_sorted_kind)) and not (i[0] in set(tmp_set)):
    tmp_set.append(i[0])
    L_sorted_.append(i)

max_score=score(L_sorted[:K])

i=1
while len(L_kind & L_sorted_kind)!=len(L_kind) and i<=K:
  if bucket[L_sorted[:K][-i][0]]>1:
    bucket[L_sorted[:K][-i][0]]-=1
    
    L_sorted[K-i]=L_sorted_[0]
    L_sorted_.pop(0)
    
    L_sorted_kind=set([i[0] for i in L_sorted[:K]])

    tmp_score=score(L_sorted[:K])
    if tmp_score>max_score:
      max_score=tmp_score
  i+=1    
  
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
import copy


def score(list):
    tl, dl = zip(*list)
    t_s = len(set(tl)) ** 2
    d_s = sum(dl)
    return t_s + d_s


def r(n, k, sl):

    for _ in range(len(sl) - k):

        ckl = {}
        for v in sl:
            if v[0] in ckl:
                if ckl[v[0]][1] > v[1]:
                    ckl[v[0]] = v
            else:
                ckl[v[0]] = v

        s_c = 0
        dtl = []
        for delckl in ckl.values():
            c_sl = copy.copy(sl)
            del c_sl[c_sl.index(delckl)]
            soe = score(c_sl)
            if s_c < soe:
                s_c = soe
                dtl = delckl

        del sl[sl.index(dtl)]

    return score(sl)


def main():
    n, k = list(map(int, input().split()))
    sl = [list(map(int, input().split())) for i in range(n)]
    print(r(n, k, sl))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def 解():
    input = sys.stdin.readline
    N,K = [int(_) for _ in input().split()]
    aP = sorted([[int(_) for _ in input().split()] for _ in range(N)],key=lambda x:x[1],reverse=True)
    dP = {}
    for t,d in aP:
        if t in dP:
            dP[t].append(d)
        else:
            dP[t] = [d]
    iSall = len(dP.keys())
    dS = set()
    aPK = aP[:K]
    for x in aPK:
        dS.add(x[0])
    iSum = sum(x[1] for x in aPK)
    i種類 = len(dS)
    iTotal = iSum + i種類**2
    if iSall == len(dS): #種類を増やす余地がない
        print(iTotal)
        exit()
    else: #種類を増やす余地があるとき
        #とりあえず地図を作る
        dPK = {}
        for t,d in aPK:
            if t in dPK :
                dPK[t].append(d)
            else:
                dPK[t] = [d]
        vT = set()
        for nt,nd in aP[K:]:
            if nt not in dS:
                for i in range(K-1,-1,-1):
                    t,d = aPK[i]
                    if t not in vT:
                        dPK[t].sort()
                        vT.add(t)
                    aT = dPK[t]
                    if 1 < len(aT):
                        iNewTotal = iSum - d + nd  + (i種類+1)**2
                        if iTotal < iNewTotal:
                            iTotal = iNewTotal
                        del dPK[t][0]
                        dPK[nt]=[nd]
                        aPK[i]=[nt,nd]
                        i種類 += 1
                        iSum = iSum -d +nd
                        dS.add(nt)
                        break
        print(iTotal)
解()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k = map(int,input().split())
l = []
for i in range(n):
    l.append(list(map(int,input().split())))
comb = list(itertools.combinations(l,k))
def calc_score(comb):
    t = set()
    d = 0
    for i in comb:
        t.add(i[0])
        d += i[1]
    return len(t) ** 2 + d
print(max([calc_score(i) for i in comb]))

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
s = [list(map(int,input().split())) for l in range(N)]
ans = []
s.sort(key = lambda x:x[1],reverse = True)
cnt = {}
A = 0
for i in range(K):
    if s[i][0] not in cnt:
        cnt[s[i][0]] = 1
    else:
        cnt[s[i][0]] += 1
    ans.append(s[i])
    A += s[i][1]
A += len(cnt)**2

ans.sort(key = lambda x:x[1])
for i in range(K,N):
    if s[i][0] not in cnt:
        for j in range(K):
            if cnt[ans[j][0]] >= 2:
                ans.pop(j)
                ans.insert(0,s[i])
                cnt[s[i][0]] = 1
                temp = 0
                for l in ans:
                    temp += l[1]
                A = max(A,temp+len(cnt)**2)
                    
                break
            
            
    else:
        continue

    if len(cnt) >= K:break
print(A)

Submission status: Time Limit Exceeded

Solution code:
from collections import  deque
N,K = map(int, input().split())
neta_uma = []
for i in range(N):
    neta,uma = map(int, input().split())
    neta_uma.append((neta, uma))
neta_uma = sorted(neta_uma, key=lambda x:x[1], reverse=True)
uma_max = [0]*(N+1) # ネタごとのうまさの最大
for neta,uma in neta_uma:
    uma_max[neta] = max(uma_max[neta], uma)
# print(uma_max)

# うまさ全振り
chosen = neta_uma[:K]
used = set(n for n,u in chosen)
# print(chosen, used)
ans = sum(u for n,u in chosen) + len(used)**2

# 多様性を増やす方向
tmp = ans
for i in range(K,N):
    # print(neta_uma[i], ans, used, )
    if not chosen: break
    
    if neta_uma[i][0] not in used:
        for j in reversed(range(len(chosen))):
            neta,uma = chosen[j]
            if uma==uma_max[neta]: continue
            chosen.remove(chosen[j])
            tmp += neta_uma[i][1] - uma
            tmp += 2*len(used) +1     # (k+1)^2 - k^2
            used.add(neta_uma[i][0])
            ans = max(ans, tmp)
            break
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

metrics = lambda x, y: x**2 + y

combs = itertools.combinations(vals, k)

max_val = 0
for c in combs:
    base = sum([val[1] for val in c])
    bonus = len(set([val[0] for val in c]))
    bonus *= bonus

    max_val = max(base + bonus, max_val)

print(max_val)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for i in range(N)]
point = [0 for i in range(K+1)]

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

eaten_sushi = [sushi[i] for i in range(K)]
eaten_variation = [s[0] for s in eaten_sushi]
variation_count = dict([(i, eaten_variation.count(i)) for i in range(1, N+1)])
variation_number = len(set(eaten_variation))
base = sum([s[1] for s in eaten_sushi])
bonus = variation_number ** 2
point[variation_number] = base + bonus


for i in range(K, N):
    if variation_count[sushi[i][0]] > 0:
        continue

    for j in range(K-1, 0, -1):
        if variation_count[eaten_sushi[j][0]] == 1:
            continue
        base = base - sushi[j][1] + sushi[i][1]
        variation_count[sushi[j][0]] += -1
        variation_count[sushi[i][0]] = 1
        eaten_sushi.pop(j)
        eaten_sushi.append(sushi[i])
        variation_number += 1
        bonus = variation_number ** 2
        point[variation_number] = base + bonus
        break

print(max(point))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for i in range(N)]
point = [0 for i in range(K+1)]

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

eaten_sushi = [sushi[i] for i in range(K)]
eaten_variation = [s[0] for s in eaten_sushi]
variation_number = len(set(eaten_variation))
base = sum([s[1] for s in eaten_sushi])
bonus = variation_number ** 2
point[variation_number] = base + bonus


for i in range(K, N):
    if sushi[i][0] in eaten_variation:
        continue

    for j in range(K-1, 0, -1):
        if eaten_variation.count(eaten_sushi[j][0]) == 1:
            continue
        base = base - sushi[j][1] + sushi[i][1]
        eaten_sushi.pop(j)
        eaten_sushi.append(sushi[i])
        eaten_variation.pop(j)
        eaten_variation.append(sushi[i][0])
        variation_number += 1
        bonus = variation_number ** 2
        point[variation_number] = base + bonus
        break

print(max(point))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for i in range(N)]
point = [0 for i in range(K+1)]

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

eaten_sushi = [sushi[i] for i in range(K)]
eaten_variation = [s[0] for s in eaten_sushi]
variation_number = len(set(eaten_variation))
base = sum([s[1] for s in eaten_sushi])
bonus = variation_number ** 2
point[variation_number] = base + bonus


for i in range(K, N):
    if sushi[i][0] in eaten_variation:
        continue

    for j in range(K-1, 0, -1):
        if eaten_variation.count(eaten_sushi[j][0]) == 1:
            continue
        eaten_sushi.pop(j)
        eaten_sushi.append(sushi[i])
        eaten_variation = [s[0] for s in eaten_sushi]
        variation_number = len(set(eaten_variation))
        base = sum([s[1] for s in eaten_sushi])
        bonus = variation_number ** 2
        point[variation_number] = base + bonus
        break

print(max(point))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
note = [list(map(int,input().split())) for i in range(N)]
note = sorted(note,key=lambda x:(x[0],-x[1]))
cnt = 0
head = []
remain = []
for i in range(N):
    if note[i][0] > cnt:
        cnt = note[i][0]
        head.append(note[i][1])
    else:
        remain.append(note[i][1])
head = sorted(head,reverse = True)
remain = sorted(remain,reverse = True)
ans = 0
for i in range(max(1,K-len(remain)),min(K,len(head))+1):
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
note = sorted([list(map(int,input().split())) for i in range(N)])
note = sorted(note,key=lambda x:(x[0],-x[1]))
cnt = 0
head = []
remain = []
for i in range(N):
    if note[i][0] > cnt:
        cnt = note[i][0]
        head.append(note[i][1])
    else:
        remain.append(note[i][1])
head = sorted(head,reverse = True)
remain = sorted(remain,reverse = True)
ans = 0
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
note = [[] for i in range(N)]
for i in range(N):
    t,d = map(int,input().split())
    t -= 1
    note[t].append(d)
head = []
remain = []
for e in note:
    if e == []:
        continue
    e.sort()
    e.reverse()
    head.append(e[0])
    if len(e) != 1:
        remain += e[1:]

head.sort()
head.reverse()
remain.sort()
remain.reverse()

ans = -float("inf")
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
max_note = [0]*N
head = []
remain = []
for i in range(N):
    t,d = map(int,input().split())
    t -= 1
    remain.append(d)
    if d > max_note[t]:
        max_note[t] = d
for e in max_note:
    if e == 0:
        continue
    head.append(e)
    remain.remove(e)

head.sort()
head.reverse()
remain.sort()
remain.reverse()

ans = -float("inf")
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(i) for i in input().split()]
td = [tuple(int(i) for i in input().split()) for i in range(N)]

def h():
    dp = {tuple(): (set(), 0)}
    end_dp = {}

    for i, (t, d) in enumerate(td):
        dp_ = dp.copy()
        for k, (t_, d_) in dp.items():
            if len(k) >= K-1:
                end_dp[k + (i,)] = (t_ | set([t]), d_ + d)
            else:
                dp_[k + (i,)] = (t_ | set([t]), d_ + d)
        dp = dp_

    return max(len(t) ** 2 + d for t, d in end_dp.values())

print(h())

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
group = [[] for i in range(N)]
for i in range(N):
    t,d = map(int,input().split())
    t -= 1
    group[t].append(d)
for e in group:
    e.sort()
    e.reverse()
head = []
remain = []
for e in group:
    if e == []:
        continue
    head.append(e[0])
    for i in range(1,len(e)):
        remain.append(e[i])
head.sort()
head.reverse()
remain.sort()
remain.reverse()
ans = -float("inf")
for i in range(1,min(K,len(head))+1):
    if K - i > len(remain):
        continue
    deli = sum(head[:i]) + sum(remain[:K-i])
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    N, K = map(int, input().split())

    lines = sys.stdin.readlines()

    all_sushi = [None] * N
    for idx, line in enumerate(lines):
        t, d = map(int, line.split())
        all_sushi[idx] = (t, d)
    all_sushi.sort(key=lambda x: x[1], reverse=True)

    sushi_A_d = {}
    sushi_B = []
    for t, d in all_sushi:
        if t not in sushi_A_d:
            sushi_A_d[t] = d
        else:
            sushi_B.append((t,d))
    sushi_A = sorted(sushi_A_d.items(), key=lambda x: x[1], reverse=True)

    prev = 0
    for i in range(min(len(sushi_A), K))[::-1]:
        a = [i[1] for i in sushi_A[:i+1]]
        b = [i[1] for i in sushi_B[:K-i-1]] if K-i-1 != 0 else [0]
        tmp = (i+1) * (i+1) + sum(a) + sum(b)
        if prev > tmp:
            break
        prev = tmp
    print(prev)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    N, K = map(int, input().split())

    lines = sys.stdin.readlines()

    all_sushi = [None] * N
    for idx, line in enumerate(lines):
        t, d = map(int, line.split())
        all_sushi[idx] = (t, d)
    all_sushi.sort(key=lambda x: x[1], reverse=True)

    sushi_A_d = {}
    sushi_B = []
    for t, d in all_sushi:
        if t not in sushi_A_d:
            sushi_A_d[t] = d
        else:
            sushi_B.append((t,d))
    sushi_A = sorted(sushi_A_d.items(), key=lambda x: x[1], reverse=True)

    max_tmp = 0
    for i in range(min(len(sushi_A), K))[::-1]:
        a = [i[1] for i in sushi_A[:i+1]]
        b = [i[1] for i in sushi_B[:K-i-1]] if K-i-1 != 0 else [0]
        tmp = (i+1) * (i+1) + sum(a) + sum(b)
        if tmp > max_tmp:
            max_tmp = tmp
    print(max_tmp)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools

def funcF(p):
    return p

def funcG(p):
    return funcF(p) + p*p


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

# print(tdList)
tdList.sort(key=lambda x: x[1])
tdList.reverse()

S = [0] * (K+1)
f = [0] * (K+1)
g = [0] * (K+1)
tmpS=[i for i in range(K)]
x=[]
tmpF=0
for i in range(K):
    tmpF += tdList[i][1]
    if tdList[i][0] not in x:
        x.append(tdList[i][0])
a=len(x)
f[a] = tmpF
g[a] = f[a] + a*a
S[a] = tmpS

for i in range(a+1, K+1):
    S[i] = copy.deepcopy(S[i-1])
    f[i] = f[i-1]
    flag = False
    tmpT=[]
    for j in range(K):
        tmpT.append(tdList[S[i][j]][0])

    for j in range(K-1, -1, -1):
        if tmpT.count(tmpT[j]) == 1:
            pass
        else:
            f[i] -= tdList[S[i][j]][1]
            del(tmpT[j])
            del(S[i][j])
            flag = True
            break
    if flag == False:
        break

    flag = False
    for j in range(max(S[i])+1, N):
        if tdList[j][0] not in tmpT:
            flag = True
            S[i].append(j)
            f[i] += tdList[j][1]
            g[i] = f[i] + i*i
            break
    if flag == False:
        break

print(max(g))



# combList = list(itertools.combinations(range(N), K))
# manzokudo=[0]*len(combList)
# for combID in range(len(combList)):
#     comb = combList[combID]
#     x=[]
#     for i in range(K):
#         manzokudo[combID] += d[comb[i]]
#         if t[comb[i]] in x:
#             pass
#         else:
#             x.append(t[comb[i]])
#     manzokudo[combID] += len(x)*len(x)
#
# print(max(manzokudo))

Submission status: Time Limit Exceeded

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

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

ans = 0
aru = []
spe = set()
m = 0

for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans+=anstmp[1]
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])

m = ans + sum(aru) + len(spe)**2

for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        aru.pop()
        ans+=nai[i][1]
        spe.add(nai[i][0])
    m = max(m, ans + sum(aru) + len(spe)**2)
print(m)

Submission status: Time Limit Exceeded

Solution code:


def solve(N, K, tds):
    tds.sort(reverse=True, key=lambda x: x[1])
    tmp_max = sum(t[1] for t in tds[:K])
    various = len(set([t[0] for t in tds[:K]]))

    has = tds[:K]
    v = {t[0]: 0 for t in tds}
    for t in has:
        v[t[0]] += 1
    has.sort(key=lambda x: x[1])

    nothas = tds[K:]
    nothas.sort(reverse=True, key=lambda x: x[1])

    mm = tmp_max + various ** 2
    for _ in range(0, 10000):
        target = None
        for i, t in enumerate(has):
            if v[t[0]] > 1:
                v[t[0]] -= 1
                tmp_max -= t[1]
                target = i
                break
        if target is not None:
            del has[target]
        else:
            break

        target = None
        for i, t in enumerate(nothas):
            if v[t[0]] == 0:
                v[t[0]] += 1
                tmp_max += t[1]
                target = i
                break
        if target is not None:
            del nothas[target]
        else:
            break

        various += 1
        mm = max(mm, tmp_max + various ** 2)

    return mm

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    tds = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, tds))

Submission status: Time Limit Exceeded

Solution code:


def solve(N, K, tds):
    tds.sort(reverse=True, key=lambda x: x[1])
    tmp_max = sum(t[1] for t in tds[:K])
    various = len(set([t[0] for t in tds[:K]]))

    has = tds[:K]
    v = {t[0]: 0 for t in tds}
    for t in has:
        v[t[0]] += 1
    has.sort(key=lambda x: x[1])

    nothas = tds[K:]
    nothas.sort(reverse=True, key=lambda x: x[1])

    mm = tmp_max + various ** 2
    for _ in range(0, 10000):
        target = None
        for t in has:
            if v[t[0]] > 1:
                v[t[0]] -= 1
                tmp_max -= t[1]
                target = t
                break
        if target:
            has.remove(target)
        else:
            break

        target = None
        for t in nothas:
            if v[t[0]] == 0:
                v[t[0]] += 1
                tmp_max += t[1]
                target = t
                break
        if target:
            nothas.remove(target)
        else:
            break

        various += 1
        mm = max(mm, tmp_max + various ** 2)

    return mm

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    tds = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, tds))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
ans = []
aru = []
nai = []
spe = set()
f = []
m = 0
for i in range(n):
    t, d = map(int, input().split())
    nai.append([t,d])
nai = sorted(nai, key=lambda x: x[1], reverse = True)
for i in range(k):
    anstmp = nai.pop(0)
    if(anstmp[0] not in spe):
        ans.append(anstmp[1])
        spe.add(anstmp[0])
    else:
        aru.append(anstmp[1])

f.append(sum(ans) + sum(aru))
s = len(spe)
for i in range(len(nai)):
    if(len(aru) == 0): break
    if(nai[i][0] not in spe):
        aru.pop(-1)
        ans.append(nai[i][1])
        spe.add(nai[i][0])
        f.append(sum(ans) + sum(aru))
for i in range(len(f)):
    m = max(m, f[i] + (s + i)**2)
print(m)

Submission status: Time Limit Exceeded

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

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

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 data[K:]:
    if not i[0] in [a[0] for a in now]:
        for j in reversed(range(K)):
            if [a[0] for a in now].count(now[j][0]) != 1:
                now = now[:j]+now[j+1:]+[i]
                break
        if p_max < count(now):
            p_max = count(now)



print(p_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from copy import deepcopy
import itertools


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def satisfy(sushis):
    t_count = len({t for i, t, d in sushis})
    d_sum = sum(d for i, t, d in sushis)
    return t_count * t_count + d_sum


def main():
    n, k = get_int_list()
    sushis = []
    for i in range(n):
        t, d = get_int_list()
        sushis.append((i, t, d))

    ss = deepcopy(sushis)
    s_dict = defaultdict(list)
    for t, s in itertools.groupby(ss, key=lambda x: x[1]):
        s_dict[t].extend(list(s))
    max_d_list = []
    remains = []
    for t in s_dict.keys():
        s_dict[t].sort(key=lambda x: x[2])
        max_d_list.append(s_dict[t].pop(-1))
        remains.extend(s_dict[t])
    max_d_list.sort(key=lambda x: x[2], reverse=True)
    remains.sort(key=lambda x: x[2], reverse=True)
    bests = []
    t_count = len(list(s_dict.keys()))
    if k > t_count:
        bests = sorted(max_d_list[:] + remains[:k-t_count], key=lambda x: x[2])
        remains = reversed(remains[k-t_count:])
    else:
        bests = reversed(max_d_list[:k])
        remains = sorted(max_d_list[k:] + remains, key=lambda x: x[2])
    bests = list(bests)
    remains = list(remains)
    while remains:
        another = bests[1:] + remains[-1:]
        if satisfy(bests) > satisfy(another):
            break
        bests = another
        remains.pop(-1)
    print(satisfy(bests))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
best_sushi = []
best_syurui = set()
other = []
for i in range(n):
    if td[i][0] in best_syurui:
        other.append(td[i][1])
    else:
        best_sushi.append(td[i][1])
        best_syurui.add(td[i][0])
best = []
for i in range(k + 1):
    MP = sum(best_sushi[:i]) + sum(other[:k - i])
    BP = len(best_sushi[:i])
    best.append(MP + BP ** 2)
print(max(best))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K = map(int,input().split())
td = np.empty((N,2),dtype=np.int64)
for i in range(N):
    td[i] = list(map(int,input().split()))

t = td[:,0]-1
d = td[:,1]
order1=np.argsort(d)[::-1]
mins = len(set(t[order1[:K]]))

best = -np.ones(N,dtype=np.int64)
for i in range(N):
    if best[t[i]] < 0 or d[i] > d[best[t[i]]]:
        best[t[i]]=i

bestmenu = np.array(list(set(best) - set([-1])),dtype=np.int64)
othermenu = np.array(list(set(range(N)) - set(bestmenu)),dtype=np.int64)

maxs = min(len(bestmenu),K)
ans = 0
bests=0
for s in range(mins,maxs+1):
    score = s*s + np.sort(d[bestmenu])[::-1][:s].sum() + np.sort(d[othermenu])[::-1][:(K-s)].sum()
    if score > ans:
        bests=s
        ans = score

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from itertools import combinations

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N, K = il()
    TD = iml(N)
    ans = 0
    for td in combinations(TD, K):
        c = Counter([td[k][0] for k in range(K)])
        x = len(c)
        tmp = x ** 2 + sum([td[k][1] for k in range(K)])
        if ans < tmp:
            ans = tmp
    return ans


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

sushi = np.array( [list(map(int, input().split())) for i in range(n)] )
index=list(range(0,n))

ans=0
for i in range(100000):
    tmp = np.random.choice(index, k, replace=False)
    sushi_ = sushi[tmp]
    ans_   = np.sum(sushi_[:,1]) + len(set(sushi_[:,0]))**2
    if ans_ > ans : ans = ans_

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import operator

N, K = map(int, input().split())
sushi = [tuple([i] + [int(x) for x in input().split()]) for i in range(N)]
sushi.sort(key=operator.itemgetter(2), reverse=True)

from collections import OrderedDict, deque, Counter
left = OrderedDict((x[0], x) for x in sushi)

base = 0
choosen = []
choosen_kind = set()
for x in sushi:
    i, t, _ = x
    if t not in choosen_kind:
        choosen.append(x)
        choosen_kind.add(t)
        del left[i]

choosen.sort(key=operator.itemgetter(2), reverse=True)
choosen = choosen[:K]
base = sum(d for _,_,d in choosen)
kinds = len(choosen)

tl = list(itertools.islice(left.values(), K))
fixed = tl[:K - len(choosen)]
cands = tl[K - len(choosen):]
base += sum(d for _,_,d in fixed)

score = base + kinds**2

if cands:
    comp = []
    while cands and cands[0][2] > choosen[-1][2]:
        base_n = base
        base_n -= choosen[-1][2]
        base_n += cands[0][2]
        kinds_n = kinds - 1
        
        score_n = base_n + kinds_n**2
        if score_n > score:
            choosen = choosen[:-1]
            fixed += cands[0]
            cands = cands[1:]
            base, kinds, score = base_n, kinds_n, score_n
        else:
            break
print(score)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

metrics = lambda x, y: x**2 + y

comb = list(itertools.combinations(vals, k))
max_val = 0
for c in comb:
    base = np.sum([val[1] for val in c])
    bonus = len(set([val[0] for val in c]))
    bonus *= bonus

    max_val = max(base + bonus, max_val)

print(max_val)