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:
from collections import defaultdict
import heapq
N,K=map(int,input().split())

hq=[]
tset_all=set()
for i in range(N):
  t,d=map(int,input().split())
  heapq.heappush(hq,(-d,t))
  tset_all.add(t)
#print(heapq)

hq_K=[]
dsum=0
tdic=defaultdict(int)
for i in range(K):
  md,t=heapq.heappop(hq)
  heapq.heappush(hq_K,((-md,t)))
  dsum-=md
  tdic[t]+=1  

t0=len(tdic)
max_answer=dsum+(t0**2)
#print(t0,max_answer)

for i in range(t0+1,min(K,len(tset_all))+1):
  loop_flg=True
  while(loop_flg):
    d,t=heapq.heappop(hq_K)
    if tdic[t]>1:
      tdic[t]-=1
      dsum-=d
      
      while(True):
        md2,t2=heapq.heappop(hq)
        if tdic[t2]==0:
          dsum-=md2
          loop_flg=False
          break
          
  answer_i=dsum+(i**2)
  #print(i,answer_i)
  max_answer=max(max_answer,answer_i)
  
print(max_answer)

Submission status: Wrong Answer

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

dtlist = []
tdlist = []
for i in range(N):
  t,d=map(int,input().split())
  dtlist.append((d,t))
  tdlist.append((t,d))
  
dtlist.sort(reverse=True)
tdlist.sort(reverse=True)
#print(dtlist)
#print(tdlist)
  
sum_d=0
set_t=set()
for i in range(K):
  d,t=dtlist[i]
  sum_d += d
  set_t.add(t)
  
print(sum_d+len(set_t)*len(set_t))

Submission status: Wrong Answer

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

dtlist = []
tdlist = []
for i in range(N):
  t,d=map(int,input().split())
  dtlist.append((d,t))
  tdlist.append((t,d))
  
dtlist.sort(reverse=True)
tdlist.sort(reverse=True)
print(dtlist)
print(tdlist)
  
sum_d=0
set_t=set()
for i in range(K):
  d,t=dtlist[i]
  sum_d += d
  set_t.add(t)
  
print(sum_d+len(set_t)*len(set_t))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

n, k = map(int, input().split())
TD = [[0, 0] for _ in range(n)]
for i in range(n):
    t, d = map(int, input().split())
    TD[i][0], TD[i][1] = d, t

TD.sort(reverse=True)
S = set()
f = 0
h = []
import heapq
heapq.heapify(h)
for i in range(k):
    d, t = TD[i]
    if t in S:
        heapq.heappush(h, d)
    else:
        S.add(t)
    f += d

INF = 10**18
F = [-INF]*(k+1)
cur = len(S)
F[cur] = f

for i in range(k, n):
    d, t = TD[i]
    print(d, t)
    if t in S:
        continue
    else:
        if h:
            x = heapq.heappop(h)
            f += d-x
            S.add(t)
            cur += 1
            F[cur] = f

for i in range(0, k+1):
    F[i] += i*i

print(max(F))

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
a = 0
ans = []
kind = [-1]*n
c = 0
min_p = deque()
for i in range(n):
    eat = False
    if i<k:
        a += td[i][1]
        eat = True
    else:
        if min_p:
            if kind[td[i][0]-1]<0:
                a -= (min_p.popleft()-td[i][1])
                a += (c+1)**2-c**2
                ans.append(a)
                eat = True
    if eat:
        if kind[td[i][0]-1]<0:
            kind[td[i][0]-1]=1
            c+=1
        else:min_p.append(td[i][1])
    if i==k-1:
        a += c**2
        ans.append(a)
print(max(ans))

Submission status: Wrong Answer

Solution code:
#tempt
N,K=map(int,input().split())
mt=0
Sushi=[]
for i in range(N):
    p,q=map(int,input().split())
    Sushi.append([p,q])
    mt=max(mt,p)

Count=[[] for i in range(mt)]

for i in range(N):
    Count[Sushi[i][0]-1].append(Sushi[i][1])
ans=0
for kind in range(1,K+1):
    tmp=kind**2

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
td=[]
for _ in range(n):
  td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
td_core=[]
td_sel=[]
td_sub=[]
cat=[0]*(n+1)
for i in range(n):
  if i < k and cat[td[i][0]]==0:
    td_core.append(td[i])
    cat[td[i][0]]=1
  elif i < k:
    td_sel.append(td[i])
  elif cat[td[i][0]]==0:
    td_sub.append(td[i])
    cat[td[i][0]]=1
# i >= k and cat[td[i][0]]==1 となるものはすでにtd_core,td_sel,td_sub内ものと種類も被っている上に美味しさも低い
# 後の工程では種類を増やす処理なので、同じ種類のネタは美味しさが最大のもの一つで十分。なので捨てる

# dの大きいじゅんに貪欲にネタを取得したときの満足ポイント
kiso=sum([x[1] for x in td_core])+sum(x[1] for x in td_sel)
bns=len(td_core)
ans=kiso+bns**2
# この状態からネタの種類を増やしていき最大が出てくるか検証
# td_sel内のネタは同一ネタが複数あり、そのネタ内で最大じゃないものが美味しさの大きい順に入っている。
# td_subにはtd_core,tdselにないネタの最大美味しさの寿司が入っている。
td_sel.sort(key=lambda x:x[0])
for i in range(min(len(td_sel),len(td_sub))):
  kiso-=td_sel[i][1]
  kiso+=td_sub[i][1]
  bns+=1
  ans=max(ans,kiso+bns**2)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td_sel=[]
td_sub=[]
td=[]
cat=[0]*(n+1)
for _ in range(n):
    t_,d_=map(int,input().split())
    td.append([t_,d_])
td.sort(key=lambda x:x[1],reverse=True)
for tdi in td:
    if cat[tdi[0]]==0 and len(td_sel)<k:
        td_sel.append(tdi)
        cat[tdi[0]]+=1
    else:
        td_sub.append(tdi)
td_sub=deque(td_sub)
n_cat=len(td_sel)
while len(td_sel)<k:
    td_sel.append(td_sub.popleft())
ans=n_cat**2 + sum([x[1] for x in td_sel])
#print(ans)
sub=0
i=0
for _ in range(min(len(td_sub),len(td_sel))):
    if cat[td_sub[0][0]]==0:
        td_sub.popleft()
        continue
    n_cat-=1
    i+=1
    sub+=td_sub[0][1]
    ans=max(ans,n_cat**2 + sum([x[1] for x in td_sel[:len(td_sel)-i]])+sub)
    td_sub.popleft()

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    g = LIR(n)
    l = list(set(([i for (i,j) in g])))
    g.sort(key=lambda x:-x[1])
    l.sort()
    q = []
    q2 = []
    f = [0]*len(l)
    ans = 0
    res = k
    for i in range(n):
        t,d = g[i]
        g[i][0] = t = bisect.bisect_left(l,t)
        if res:
            f[t] = 1
            ans += d
            heappush(q,(d,t))
            res -= 1
        else:
            heappush(q2,(-d,t))
    x = sum(f)
    ans += x**2
    s = ans
    while q2:
        d,t = heappop(q2)
        d *= -1
        if f[t]:
            continue
        else:
            s -= heappop(q)[0]
            s += 2*x+1
            s += d
            x += 1
            heappush(q,(d,t))
            f[t] = 1
            if ans < s:
                ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    g = LIR(n)
    l = list(set(([i for (i,j) in g])))
    l.sort()
    q = []
    q2 = []
    f = [0]*len(l)
    ans = 0
    res = k
    for i in range(n):
        t,d = g[i]
        g[i][0] = t = bisect.bisect_left(l,t)
        if res:
            f[t] += 1
            ans += d
            res -= 1
            if f[t] > 1:
                heappush(q,(d,t))
        else:
            heappush(q2,(-d,t))
    x = sum([i >= 1 for i in f])
    ans += x**2
    s = ans
    while q2 and q:
        d,t = heappop(q2)
        d *= -1
        if f[t]:
            continue
        else:
            nd,nt = heappop(q)
            s -= nd
            s += 2*x+1
            s += d
            x += 1
            f[t] = 1
            f[nt] -= 1
            if ans < s:
                ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    g = LIR(n)
    l = list(set(([i for (i,j) in g])))
    l.sort()
    q = []
    q2 = []
    f = [0]*len(l)
    ans = 0
    res = k
    for i in range(n):
        t,d = g[i]
        g[i][0] = t = bisect.bisect_left(l,t)
        if res:
            f[t] = 1
            ans += d
            heappush(q,(d,t))
            res -= 1
        else:
            heappush(q2,(-d,t))
    x = sum(f)
    ans += x**2
    s = ans
    while q2:
        d,t = heappop(q2)
        d *= -1
        if f[t]:
            continue
        else:
            s -= heappop(q)[0]
            s += 2*x+1
            s += d
            x += 1
            heappush(q,(d,t))
            f[t] = 1
            if ans < s:
                ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

base = 0
kind = 0

#kind

td.sort(reverse=True)

t = 0
groupf=[]
groups=[]
for i in range(N):
  if td[i][0] != t:
    groupf.append(td[i][1])
    t = td[i][0]
  else:
    groups.append(td[i][1])


if K >= len(groupf):
  kind += sum(groupf)
  groups.sort(reverse=True)
  kind += sum(groups[:(K-len(groupf))])
  kind += len(groupf)**2

else:
  groupf.sort(reverse=True)
  kind += sum(groupf[:K])
  kind += K*K


#base

t = 0
td.sort(key=lambda x: x[1], reverse=True)

check_t = []
for i in range(N):
  check_t.append(0)

for i in range(K):
  base += td[i][1]
  if check_t[(td[i][0])-1] == 0:
    check_t[(td[i][0])-1] = 1
    t += 1


base += t**2


print(max(kind,base))

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-td[now][1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
l=0
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
        l+=1
ans+=(l*l)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
l=0
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
        l+=1
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1+mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(n-1,k-1,-1):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[td[now][0]]-=1
                break
            now-=1
        else:
            break
        ans=ans-2*l+1-mi[1]+td[i][1]
        kl[td[i][0]]=1
        ans_=max(ans,ans_)
        l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kindsl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kindsl:
        kindsl[td[i][0]]+=1
    else:
        kindsl[td[i][0]]=1
l=len(kindsl)
ans+=(l**2)
inf=10**20
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kindsl:
        mi=[inf,inf]
        #最小を求めるのをもっと早く
        while now>=0:
            if kindsl[td[now][0]]>1:
                mi=td[now]
                kindsl[td[now][0]]-=1
                break
            now-=1
        if mi==[inf,inf]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kindsl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
kindsl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]+=1
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]=1
l=len(kinds)
ans+=(l**2)
inf=10**20
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[inf,inf]
        #最小を求めるのをもっと早く
        while now>=0:
            if kindsl[td[now][0]]>1:
                mi=td[now]
                kindsl[td[now][0]]-=1
                break
            now-=1
        if mi==[inf,inf]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            kindsl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
kindsl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]+=1
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]=1
l=len(kinds)
ans+=(l**2)
inf=10**20
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[inf,inf]
        #最小を求めるのをもっと早く
        '''
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        '''
        while now>0:
            if kindsl[td[now][0]]>1:
                mi=td[now]
                kindsl[td[now][0]]-=1
                break
            now-=1
        if mi==[inf,inf]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            kindsl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
kindsl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]+=1
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]=1
l=len(kinds)
ans+=(l**2)
inf=10**13
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[inf,inf]
        #最小を求めるのをもっと早く
        '''
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        '''
        while now>0:
            if kindsl[td[now][0]]>1:
                mi=td[now]
                kindsl[td[now][0]]-=1
                break
            now-=1
        if mi==[inf,inf]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            kindsl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
kindsl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]+=1
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
        kindsl[td[i][0]]=1
l=len(kinds)
ans+=(l**2)

ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        #最小を求めるのをもっと早く
        '''
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        '''
        while now>0:
            if kindsl[td[now][0]]>1:
                mi=td[now]
                kindsl[td[now][0]]-=1
                break
            now-=1
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            kindsl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
l=len(kinds)
ans+=(l**2)
#kindsの中はソートされている状況
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            kinds[td[i][0]]=[td[i][1]]
            ans_.append(ans)

print(max(ans_))

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=[td[i][1]]
l=len(kinds)
ans+=(l**2)
#kindsの中はソートされている状況
ans_=[ans]
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kinds[mi[0]].pop(-1)
            l+=1
            ans_.append(ans)
print(max(ans_))

Submission status: Wrong Answer

Solution code:

n,k= map(int,input().split())
td=[]
for _ in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
NEW=[1]*(n+1)
x=0
y=0
TOP=[]
SUB=[]
for tdi in td[:k]:
    if NEW[tdi[0]]==1:
        NEW[tdi[0]]=0
        y+=1
    x+=tdi[1]
    TOP.append(tdi[1])
for tdi in td[k:]:
    if NEW[tdi[0]]==1:
        SUB.append(tdi[1])
        NEW[tdi[0]]=0
ans=x+y**2
for i in range(min(k,len(SUB))):
    x -= TOP.pop()
    x += SUB[i]
    y += 1
    ans = max(ans,x+y**2)
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if len(select) % 3 == 1:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

print(8)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
print(8)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

print(8)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
print(8)

Submission status: Wrong Answer

Solution code:
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=td[:k]
cat=list(set([tdi[0] for tdi in select]))
noselect=[]
for no in td[k:]:
    if no[0] in cat:
        continue
    noselect.append(no)
rs=[]
rs.append(sum([tdi[1] for tdi in select])+len(set([tdi[0] for tdi in select]))**2)
for i in range(1,min(k,len(noselect)+1)):
    t = select[:-i]
    t[k-i:k-i] = noselect[:i]
    r = sum([tdi[1] for tdi in t])
    r += len(set([tdi[0] for tdi in t]))**2
    rs.append(r)
print(max(rs))

Submission status: Wrong Answer

Solution code:

#from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
#td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat or len(select)==k:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
#select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
i=0
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[i][1]:
        select[i]=no
        i+=1
        #select.popleft()
        #select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))