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: Accepted

Solution code:
N,K=map(int,input().split())
b=[] #[[種類,美味しさ],...]
 
for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
b.sort(key=lambda x:-x[1])
 
f=[0]*(N+1)
x=0
point=0
 
for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x
 
h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h = i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Submission status: Accepted

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

L = sorted(L, key = lambda x:(x[0], -x[1]))
for i in range(N):
    if i == 0:
        ra = 0
        L[i] = (L[i][0], L[i][1], ra)
    else:
        if L[i][0] == L[i-1][0]:
            ra += 1
        else:
            ra = 0
        L[i] = (L[i][0], L[i][1], ra)

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

if N != K:
    kouho = L[:K]
    amari = L[K:]
else:
    kouho = L
    
nowval = len(set([sushi[0] for sushi in kouho]))
nowder = sum([sushi[1] for sushi in kouho])
point = nowval ** 2 + nowder

if N == K:
    print(point)
else:
    weaks = []
    for sushi in kouho:
        if sushi[2] > 0:
            weaks.append(sushi)
    weaks.reverse()
    kaburan = []
    for sushi in amari:
        if sushi[2] == 0:
            kaburan.append(sushi)
    
    ma = min(len(weaks), len(kaburan))
    newpoint = point
    if ma:
        for i in range(ma):
            newpoint = newpoint - weaks[i][1] + kaburan[i][1]
            newpoint = newpoint - nowval ** 2 + (nowval + 1) ** 2
            nowval += 1
            point = max(point, newpoint)
        print(point)
    else:
        print(point)

Submission status: Accepted

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)
    dS = set()
    aPK = aP[:K]
    for t,d in aPK:
        dS.add(t)
    dSall = dS.copy()
    for t,d in aP[K:]:
        dSall.add(t)
    iSall = len(dSall)

    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()
        j = K - 1
        for nt,nd in aP[K:]:
            if i種類 == iSall:
                break
            if nt not in dS:
                #for i in range(K-1,-1,-1):
                for i in range(j,-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
                j=i-1
        print(iTotal)
解()

Submission status: Accepted

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()
        j = K - 1
        for nt,nd in aP[K:]:
            if i種類 == iSall:
                break
            if nt not in dS:
                #for i in range(K-1,-1,-1):
                for i in range(j,-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
                j=i-1
        print(iTotal)
解()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    dt = sorted([LI()[::-1] for _ in range(n)], reverse=True)

    u = set()
    s = 0
    o = []
    for d,t in dt[:k]:
        if t in u:
            o.append(d)
        else:
            u.add(t)
        s += d
    r = s + len(u) ** 2
    oi = len(o) - 1
    for d,t in dt[k:]:
        if oi < 0:
            break
        if t in u:
            continue
        s -= o[oi]
        oi -= 1
        s += d
        u.add(t)
        tr = s + len(u) ** 2
        if r < tr:
            r = tr

    return r



print(main())

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from operator import itemgetter
input = sys.stdin.readline

N, K = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]
TD.sort(reverse=True, key=itemgetter(1))

selected = Counter()
ans = 0
stack = []

for t, d in TD[:K]:
    ans += d
    selected[t] += 1
    stack.append((t, d))
ans += len(selected) ** 2

tmp = ans
for t, d in TD[K:]:
    if t in selected:
        continue
    while stack:
        t0, d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2 * len(selected) + 1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
def d_various_sushi(N, K, Param):
    import heapq

    # 寿司をおいしさの値が大きなものからK個取る
    sushi_parameter = sorted(Param, key=lambda x: x[1], reverse=True)
    sushi_invariably_chosen = []  # ネタが被っていない場合、貪欲に取っていい
    candidate_reject = []  # ネタの種類数を増やす時に取り除く候補(priority queueで管理)
    chosen_topping = set()  # 取った寿司ネタの種類
    for i in range(K):
        t, d = sushi_parameter[i]
        if t not in chosen_topping:
            sushi_invariably_chosen.append(d)
            chosen_topping.add(t)
        else:
            heapq.heappush(candidate_reject, d)

    # 暫定的な最大値を計算しておく
    delicious_sum1 = sum(sushi_invariably_chosen)
    delicious_sum2 = sum(candidate_reject)
    topping_variety = len(chosen_topping)
    ans = delicious_sum1 + delicious_sum2 + topping_variety**2

    for i in range(K, N):
        if len(candidate_reject) == 0:
            break  # 除く寿司の候補がないので、満足度を大きくしようがない

        t, d = sushi_parameter[i]
        if t in chosen_topping:
            # ネタが被った上、おいしさがこれまで取った寿司より小さな寿司と交換する理由はない
            continue

        # 取り除いてもネタの種類数が減らない寿司の中で最もおいしさの小さいものを取り除く
        delicious_sum2 -= heapq.heappop(candidate_reject)
        # これまでに取っている寿司にないネタを持ち、最もおいしさの大きい寿司を取る
        chosen_topping.add(t)
        delicious_sum1 += d
        topping_variety += 1

        ans = max(ans, delicious_sum1 + delicious_sum2 + topping_variety**2)
    return ans

N, K = [int(i) for i in input().split()]
Param = [[int(i) for i in input().split()] for j in range(N)]
print(d_various_sushi(N, K, Param))

Submission status: Accepted

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

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


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

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

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

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

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

Submission status: Accepted

Solution code:
from sys import exit

N,K=map(int,input().split())
b=[] #[[種類,美味しさ],...]

for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
b.sort(key=lambda x:-x[1])

f=[0]*(N+1)
x=0
point=0

for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x

h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h=i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Submission status: Accepted

Solution code:
from sys import exit

N,K=map(int,input().split())
a={} #{種類:美味しさ}
b=[] #[[種類,美味しさ],...]

for _ in range(N):
    t,d=map(int,input().split())
    b.append([t,d])
    try:
        a[t].append(d)
    except KeyError:
        a[t]=[d]
b.sort(key=lambda x:-x[1])

f=[0]*(N+1)
x=0
point=0
pointsum=[]

for [t,d] in b[:K]:
    if f[t]==0: x+=1
    f[t]+=1
    point+=d
maxpoint=point+x*x

h=K-1
for [t,d] in b[K:]:
    if f[t]==0:
        f[t]=1
        x+=1
        point+=d
        for i in range(h,-2,-1):
            if i==-1:
                print(maxpoint)
                exit()
            t=b[i][0]
            d=b[i][1]
            if f[t]>1:
                f[t]-=1
                point-=d
                h=i-1
                break
        maxpoint=max(maxpoint,point+x*x)
print(maxpoint)

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
TD = [[int(_) for _ in input().split()] for i in range(N)]
 
# print(TD)
 
xs = sorted(TD, key=lambda x:-x[1])
 
#print(xs)
 
baset = 0
ts = set()
ds = []
 
for t, d in xs[:K]:
    baset += d
    if not t in ts:
        ts.add(t)
    else:
        ds.append(d)
result = baset + len(ts)**2
r = result

for t, d in xs[K:]:
    if not ds:
        break
    if t not in ts:
        r += 2*len(ts) + 1
        r += d - ds.pop()
        ts.add(t)
        result = max(r,result)

print(result)

Submission status: Accepted

Solution code:
from heapq import*
I=lambda:list(map(int,input().split()))[::-1]
k,n=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for b,a in sorted(I()for _ in[0]*n)[::-1]:
 if i<k:
  if l[a]:heappush(q,b)
  else:T+=v*2+1;v+=1
  T+=b
 elif l[a]^1and q:T+=b+v*2+1-heappop(q);v+=1
 A=max(A,T);i+=1;l[a]=1
print(A)

Submission status: Accepted

Solution code:
from heapq import*
I=lambda:list(map(int,input().split()))
n,k=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:heappush(q,b)
  else:T+=v*2+1;v+=1
  T+=b
 elif l[a]^1and q:T+=b+v*2+1-heappop(q);v+=1
 A=max(A,T);i+=1;l[a]=1
print(A)

Submission status: Accepted

Solution code:
import heapq as h
I=lambda:list(map(int,input().split()))
n,k=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=v*2+1;v+=1
  T+=b
 elif l[a]^1and q:T+=b+v*2+1-h.heappop(q);v+=1
 A=max(A,T);i+=1;l[a]=1
print(A)

Submission status: Accepted

Solution code:
import heapq as h
I=lambda:list(map(int,input().split()))
n,k=I()
q=[]
v=i=T=A=0
l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=v*2+1;v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+v*2+1-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];q=[];v=i=T=A=0;l=[0]*-~n
for a,b in sorted([I()for _ in[0]*n],key=lambda x:-x[1]):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=i=T=A=0;l=[0]*-~n
for a,b in s:
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T);i+=1
print(A)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=T=A=0;l=[0]*-~n
for i,(a,b)in enumerate(s):
 if i<k:
  if l[a]:h.heappush(q,b)
  else:T+=z[v];v+=1
  l[a]=1;T+=b
 elif l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1
 A=max(A,T)
print(A)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n,k=[int(i) for i in input().split()]

td = []
for _ in range(n):
    t,d= [int(i) for i in input().split()]
    td.append([t-1,d])


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


greedy = []
c=0
oisi = [0]*n
neta = [0]*n
ans = 0
for i in range(k):
    t_temp = td[i][0]
    d_temp = td[i][1]
#    print(neta,t_temp)
    ans += d_temp
    if neta[t_temp] == 0:
        c+=1
        oisi[t_temp] = d_temp
        neta[t_temp] += 1
    else:
        if oisi[t_temp] > d_temp:
            greedy.append(d_temp)
        else:
            greedy.append(oisi[t_temp])
            oisi[t_temp] = d_temp


#print(td)
ans += c*c
#print(c,ans)

amari=[]
for i in range(k,n):
    t_temp= td[i][0]
#    print(neta,t_temp)
    if neta[t_temp] == 0:
        amari.append(td[i][1])
        neta[t_temp] += 1

greedy.sort(reverse=True)
amari.sort()

#print(greedy)
#print(amari)

temp=ans
while(len(greedy)!= 0 and len(amari)!=0):
    a=greedy.pop()
    b=amari.pop()
    temp += b-a+2*c+1
    if ans < temp:
        ans = temp
    c+=1

print(ans)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=A=0;l=[0]*-~n
for a,b in s[:k]:
 if l[a]:h.heappush(q,b)
 else:A+=z[v];v+=1
 l[a]=1;A+=b
T=A
for a,b in s[k:]:
 if l[a]^1and q:l[a]=1;T+=b+z[v]-h.heappop(q);v+=1;A=max(A,T)
print(A)

Submission status: Accepted

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

# おいしさ順にソート
sushi.sort(key=lambda x: x[1], reverse=True)

# 取りうる最大の種類数
MAX_various = min(K, len(set([t for t, d in sushi])))

# 食べる寿司を管理
eat = []
# 食べた寿司の種類を管理
various = set()
# 食べなかった寿司を管理
remain_sushi = []

score = 0
# 最大種類食べる
cnt = 0
for t, d in sushi:
    if (t not in various) and (cnt != MAX_various):
        score += d
        heapq.heappush(eat, d)
        various.add(t)
        cnt += 1
    else:
        remain_sushi.append([t, d])

score += len(various) ** 2

# 最大種類食べてもK個食べたことにならない場合、不足分をここで補充
for t, d in remain_sushi[:K - MAX_various]:
    score += d
    heapq.heappush(eat, d)
remain_sushi = remain_sushi[K - MAX_various:]

# 残り物でおいしい順に、寿司を交換しながら一番いい解を探す
ans = score
various = len(various)
for t, d in remain_sushi:
    add_ans = ans - eat[0] + d - (various ** 2) + (various - 1) ** 2
    if add_ans > ans:
        heapq.heapreplace(eat, d)
        ans = add_ans
        various -= 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind-1] + d[i] - tmp)
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Submission status: Accepted

Solution code:
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
for i in range(K, N):
    if not q:
        break
    if t[i] not in s:
        s.add(t[i])
        tmp = q.pop()
        kind += 1
        sums.append(sums[kind-1] + d[i] - tmp)
#while q:
#    kind += 1
#    tmp = q.pop()
#    for i in range(now, N):
#        now += 1
#        if t[i] not in s:
#            s.add(t[i])
#            sums.append(sums[kind-1] + d[i] - tmp)
#            break
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Submission status: Accepted

Solution code:
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
#for i in range(K, N):
#    if not q:
#        break
#    if t[i] not in s:
#        s.
while q:
    kind += 1
    tmp = q.pop()
    for i in range(now, N):
        now += 1
        if t[i] not in s:
            s.add(t[i])
            sums.append(sums[kind-1] + d[i] - tmp)
            break
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
sushi_list = []
max_d = [0] * N
for i in range(N):
    t, d = map(int, input().split())
    sushi_list.append((t - 1, d))
    max_d[t - 1] = max(max_d[t - 1], d)

sushi_list.sort(key=lambda x: x[1], reverse=True)
good = []
for i in range(N):
    if max_d[sushi_list[i][0]] == sushi_list[i][1]:
        good.append(True)
        max_d[sushi_list[i][0]] = 0
    else:
        good.append(False)

s = sum([sushi[1] for sushi in sushi_list[:K]])
p = len(set([sushi[0] for sushi in sushi_list[:K]]))
ans = s + p**2
r = K - 1
l = K
while True:
    while r >= 0 and good[r]:
        r -= 1
    while l < N and not good[l]:
        l += 1
    if r < 0 or l >= N:
        break
    s = s - sushi_list[r][1] + sushi_list[l][1]
    p += 1
    ans = max(ans, s + p**2)
    r -= 1
    l += 1

print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python

from collections import Counter

N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))


ans += len(selected)**2
# exit(0)

tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,K = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:-x[1])

selected = Counter()
ans = 0
stack = []

for t,d in src[:K]:
    ans += d
    selected[t] += 1
    stack.append((t,d))
ans += len(selected)**2

tmp = ans
for t,d in src[K:]:
    if t in selected: continue
    while stack:
        t0,d0 = stack.pop()
        if selected[t0] > 1:
            tmp += d - d0 + 2*len(selected)+1
            ans = max(ans, tmp)
            selected[t0] -= 1
            selected[t] += 1
            break
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
t=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    t[i],d[i]=map(int,input().split())
D=dict()
for i in range(N):
    if not(t[i] in D):
        D[t[i]]=[]
    D[t[i]].append((d[i],i))
E=[0 for i in range(N)]
for key in D:
    D[key].sort(reverse=True)
    E[D[key][0][1]]=1
A=[]
B=[]
for i in range(N):
    if E[i]==1:
        A.append(d[i])
    else:
        B.append(d[i])
A.sort(reverse=True)
B.sort(reverse=True)
X=len(A)
Y=len(B)
S=[0 for i in range(X+1)]
T=[0 for i in range(Y+1)]
for i in range(X):
    S[i+1]=A[i]+S[i]
for i in range(Y):
    T[i+1]=B[i]+T[i]
L=[]
for i in range(1,K+1):
    if i<=X and K-i<=Y:
        L.append(S[i]+T[K-i]+i*i)
print(max(L))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
n,k = map(int, input().split())
td = []

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

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

used = set()
q = []
res = 0
kind = 0
for i in range(k):
    t,d = td[i]
    if t not in used:
        kind += 1
        used.add(t)
    else:
        q.append((t,d))
    res += d
res += kind**2
q = deque(sorted(q, key=lambda x:x[1]))

tmp = res
for i in range(k,n):
    if len(q)==0:
        break
    t2,d2 = td[i]
    if t2 in used:
        continue
    used.add(t2)
    t,d = q.popleft()

    r = tmp - d + d2
    r -= kind**2
    kind += 1
    r += kind**2
    res = max(res, r)
    tmp = r

print(res)

Submission status: Accepted

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
acc_head = [0]
acc_remain = [0]
tmp_head = 0
tmp_remain = 0
for i in range(len(head)):
    tmp_head += head[i]
    acc_head.append(tmp_head)
for i in range(len(remain)):
    tmp_remain += remain[i]
    acc_remain.append(tmp_remain)
for i in range(max(0,K-len(remain)),min(K,len(head))+1):
    deli = acc_head[i] + acc_remain[K-i]
    kind = i**2
    res = deli + kind
    if res > ans:
        ans = res
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
n, k = map(int, input().split())
A = []
for _ in range(n):
    t, d = map(int, readline().split())
    A.append((d, t))
A.sort(reverse=True)
X = []
Y = []
st = set()
for i in range(k):
    d, t = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)
x = sum(X)
y = sum(Y)
v = len(Y)
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    d, t = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = []
for _ in range(n):
    t, d = map(int, input().split())
    A.append((d, t))
A.sort(reverse=True)
X = []
Y = []
st = set()
for i in range(k):
    d, t = A[i]
    if t in st:
        X.append(d)
    else:
        Y.append(d)
        st.add(t)
x = sum(X)
y = sum(Y)
v = len(Y)
ans = x + y + v ** 2
for i in range(k, n):
    if not X:
        break
    d, t = A[i]
    if t in st:
        continue
    st.add(t)
    x -= X.pop()
    y += d
    v += 1
    ans = max(ans, x + y + v ** 2)
print(ans)

Submission status: Accepted

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
n,k=IL()
top=dict()
sub=[]
for i in range(n):
    t,d=IL()
    if t in top:
        sub.append(min(top[t],d))
        top[t]=max(top[t],d)
    else:
        top[t]=d

top=sorted(top.items(),key=lambda x:-x[1])
sub.sort(reverse=True)

rtop=[top[0][1]]
rsub=[0]
for i in range(1,len(top)):
    rtop.append(rtop[-1]+top[i][1])
for i in range(len(sub)):
    rsub.append(rsub[-1]+sub[i])

ans=0
for i in range(k):
    if i<len(rtop) and 0<=k-i-1<len(rsub):
        ans=max(ans,rtop[i]+rsub[k-i-1]+(i+1)**2)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n, k = map(int, input().split())
sushi = []
for line in sys.stdin.readlines():
    t, d = map(int, line.split())
    sushi.append((d, t))
sushi.sort(reverse=True)

deli = 0
cnt = defaultdict(lambda: 0)
using = sushi[:k]

for d, t in sushi[:k]:
    deli += d
    cnt[t] += 1

types = len(cnt)
ans = deli + types ** 2

for d, t in sushi[k:]:
    if cnt[t] > 0:
        continue
    d2, t2 = None, None
    while using:
        d2, t2 = using.pop()
        if cnt[t2] > 1:
            break
    else:
        break
    cnt[t2] -= 1
    cnt[t] += 1
    types += 1
    deli += d - d2
    ans = max(ans, deli + types ** 2)

print(ans)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=A=0;l=[0]*-~n
for a in s[:k]:
 if l[a[0]]:h.heappush(q,a[1])
 else:A+=z[v];v+=1
 l[a[0]]=1;A+=a[1]
T=A
for a in s[k:]:
 if q and l[a[0]]^1:l[a[0]]=1;t=h.heappop(q);T=T-t+a[1]+z[v];v+=1;A=max(A,T)
print(A)

Submission status: Accepted

Solution code:
from operator import itemgetter

n, k = map(int, input().split(" "))
sushis = [list(map(int, input().split(" "))) for i in range(n)]
flags = [False for i in range(n+10)]

# calc score
sushis = sorted(sushis, key=itemgetter(1), reverse=True)
duplicated_set = []
variety = 0
eat = 0
max_score = 0
sum1 = 0
for i, sushi in enumerate(sushis):
    t, d = sushi
    if eat < k:
        sum1 += d
        eat += 1
        if flags[t]:
            duplicated_set.append(d)
        else:
            variety += 1
            flags[t] = True
        if eat == k:
            sum1 += variety * variety
            max_score = sum1
            duplicated_set = sorted(duplicated_set, reverse=True)
    else:
        if variety == k or len(duplicated_set) == 0:
            break
        if flags[t]:
            pass
        else:
            variety += 1
            flags[t] = True
            sum1 = sum1 + d - duplicated_set.pop() + 2*(variety) - 1
            max_score = max(max_score, sum1)

print(max_score)

Submission status: Accepted

Solution code:
import heapq as h;I=lambda:list(map(int,input().split()));n,k=I();z=[i*2+1for i in range(n)];s=sorted([I()for _ in[0]*n],key=lambda x:-x[1]);q=[];v=A=0;l=[0]*-~n
for a in s[:k]:
 if l[a[0]]:h.heappush(q,a[1])
 else:A+=z[v];v+=1
 l[a[0]]=1;A+=a[1]
T=A
for a in s[k:]:
 if not q:break
 if l[a[0]]^1:l[a[0]]=1;t=h.heappop(q);T=T-t+a[1]+z[v];v+=1;A=max(A,T)
print(A)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
a.sort(key=lambda x:-x[1])
ans = 0
s = set()
q = []
for i in range(k):
    ans += a[i][1]
    if a[i][0] in s:
        q.append(a[i][1])
    s.add(a[i][0])
ans += len(s)**2
ans1 = ans
k1 = k
while k1 < n and q:
    if not a[k1][0] in s:
        ans1 += a[k1][1] - q.pop() + 2*len(s) + 1
        ans = max(ans,ans1)
        s.add(a[k1][0])
    k1 +=  1
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,k=map(int,input().split())
z=[0,1]
for i in range(1,n):
    z.append(z[i]+2)
s=sorted([list(map(int,input().split()))for _ in range(n)],key=lambda x:-x[1])
q=[]
v=0
ans=0
l=[0]*-~n
for a in s[:k]:
    if not l[a[0]]:
        v+=1
        ans+=z[v]
    else:
        heapq.heappush(q,a[1])
    l[a[0]]=1
    ans+=a[1]
tem=ans
for a in s[k:]:
    if not q:break
    if l[a[0]]:continue
    l[a[0]]=1
    v+=1
    t=heapq.heappop(q)
    tem=tem-t+a[1]+z[v]
    ans=max(ans,tem)
print(ans)