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: Runtime Error

Solution code:
import  collections
class Sushi(object):
    def __init__(self,lines):
        neta,oishisa=map(int,lines.split())
        self.neta=neta
        self.oishisa=oishisa
    def __str__(self):
        return "寿司:{0} 美味しさ:{1}".format(self.neta,self.oishisa)

def score_out(eat_list):
    score=0
    items=list(collections.Counter([i.neta for i in eat_list]).items())
    score+=len(items)**2
    basic_points=[i.oishisa for i in eat_list]
    score+=sum(basic_points)

    return score

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

sushi_list=[Sushi(input()) for _ in range(N)]

sushi_list.sort(key= lambda  x:x.oishisa)

eat_list=[]

neta_max=len(list(collections.Counter([i.neta for i in sushi_list]).items()))


for i in range(K):
    eat_list.append(sushi_list.pop())
    #print(eat_list[i])

eat_items=list(collections.Counter([i.neta for i in eat_list]).items())

if len(eat_items)==K:
    print(score_out(eat_list))
    exit(0)

low_band_types=len(eat_items)

maxscore=score_out(eat_list)
for i in range(N):
    # 寿司が全て独立しているか判断する。
    # 独立してたら終了させる。
    # 寿司屋のネタの最大種類==選択したネタが最大種類でも終了
    eat_list.sort(key=lambda x:x.oishisa)
    #print ( '現在の寿司' )
    for i in eat_list:
        #print(i)
        pass
    #print('\n')

    if len(list(collections.Counter([i.neta for i in eat_list]).items()))==K and maxscore<=score_out(eat_list):
        print(score_out(eat_list))
        exit(0)
    elif len(list(collections.Counter([i.neta for i in eat_list]).items()))==neta_max and maxscore<=score_out(eat_list):
        print(score_out(eat_list))
        exit(0)

    eat_items = list ( collections.Counter ( [ i.neta for i in eat_list ] ).items ( ) )
    neta_kaburi_list=[i[0] for i in eat_items if i[1]>1]
    #print(neta_kaburi_list)
    min_oishisa=-1
    kick_avails=[]
    for kaburi_neta in neta_kaburi_list:
        kick_avails+=[i for i in eat_list if i.neta==kaburi_neta]
    kick_avails.sort(key=lambda x:x.oishisa,reverse=True)
    if not kick_avails:
        print(maxscore)
        exit(0)
    kick=kick_avails.pop()
    #print('kick as')
    #print(kick)
    eat_list.remove(kick)
    sushi_list.sort(key= lambda x:x.oishisa)
    ef=True
    neta_list = [ i[ 0 ] for i in eat_items ]

    if not sushi_list:
        print(maxscore)
        exit(0)


    while ef:
        eat_list.sort( key=lambda x: x.oishisa,reverse=True)
        sushi=sushi_list.pop()
        #print('poped sushi is ')
        #print(sushi)
        if sushi.neta in neta_list:
            pass
        else:

            eat_list.append(sushi)
            ef=False

    if score_out(eat_list)>maxscore:
        maxscore=score_out(eat_list)

print(maxscore)

Submission status: Runtime Error

Solution code:
import  collections
class Sushi(object):
    def __init__(self,lines):
        neta,oishisa=map(int,lines.split())
        self.neta=neta
        self.oishisa=oishisa
    def __str__(self):
        return "寿司:{0} 美味しさ:{1}".format(self.neta,self.oishisa)

def score_out(eat_list):
    score=0
    items=list(collections.Counter([i.neta for i in eat_list]).items())
    score+=len(items)**2
    basic_points=[i.oishisa for i in eat_list]
    score+=sum(basic_points)

    return score

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

sushi_list=[Sushi(input()) for _ in range(N)]

sushi_list=sorted(sushi_list,key= lambda  x:x.oishisa)

eat_list=[]

neta_max=len(list(collections.Counter([i.neta for i in sushi_list]).items()))


for i in range(K):
    eat_list.append(sushi_list.pop())
    #print(eat_list[i])

eat_items=list(collections.Counter([i.neta for i in eat_list]).items())

if len(eat_items)==K:
    print(score_out(eat_list))
    exit(0)

low_band_types=len(eat_items)

maxscore=score_out(eat_list)
for i in range(N):
    # 寿司が全て独立しているか判断する。
    # 独立してたら終了させる。
    # 寿司屋のネタの最大種類==選択したネタが最大種類でも終了
    eat_list=sorted(eat_list,key=lambda x:x.oishisa)
    #print ( '現在の寿司' )
    for i in eat_list:
        #print(i)
        pass
    #print('\n')

    if len(list(collections.Counter([i.neta for i in eat_list]).items()))==K and maxscore<=score_out(eat_list):
        print(score_out(eat_list))
        exit(0)
    elif len(list(collections.Counter([i.neta for i in eat_list]).items()))==neta_max and maxscore<=score_out(eat_list):
        print(score_out(eat_list))
        exit(0)

    eat_items = list ( collections.Counter ( [ i.neta for i in eat_list ] ).items ( ) )
    neta_kaburi_list=[i[0] for i in eat_items if i[1]>1]
    #print(neta_kaburi_list)
    min_oishisa=-1
    kick_avails=[]
    for kaburi_neta in neta_kaburi_list:
        kick_avails+=[i for i in eat_list if i.neta==kaburi_neta]
    kick_avails=sorted(kick_avails,key=lambda x:x.oishisa,reverse=True)
    if not kick_avails:
        print(maxscore)
        exit(0)
    kick=kick_avails.pop()
    #print('kick as')
    #print(kick)
    eat_list.remove(kick)
    sushi_list=sorted(sushi_list,key= lambda x:x.oishisa)
    ef=True
    neta_list = [ i[ 0 ] for i in eat_items ]

    if not sushi_list:
        print(maxscore)
        exit(0)


    while ef:
        eat_list = sorted ( eat_list, key=lambda x: x.oishisa,reverse=True)
        sushi=sushi_list.pop()
        #print('poped sushi is ')
        #print(sushi)
        if sushi.neta in neta_list:
            pass
        else:

            eat_list.append(sushi)
            ef=False

    if score_out(eat_list)>maxscore:
        maxscore=score_out(eat_list)

print(maxscore)

Submission status: Runtime Error

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)
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: Runtime Error

Solution code:
N, K = map(int, input().split())
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)
 
L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
ans = []
etc = []
dic = {}
ind = {}
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
for t in dic.keys():
    dic[t].sort(reverse=True)
    for i,n in enumerate(dic[t]):
      if i == 0:
          ans.append((n, 1))
      else:
          etc.append((n, 0))
ans_all = calc_ans(ans)
ans.sort(reverse=True)
etc.sort(reverse=True)
for n in etc:
    if ans[-1][1] == 0 and ans[-1][0] >= n[0]:
        break
    ans[-1] = n
    tmp = calc_ans(ans)
    if ans_all < tmp:
        ans_all = tmp
    ans.sort(reverse=True)
print(ans_all)

Submission status: Runtime Error

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)
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: Runtime Error

Solution code:
N, K = map(int, input().split())
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
ans = []
etc = []
dic = {}
ind = {}
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
for t in dic.keys():
    dic[t].sort(reverse=True)
    for i,n in enumerate(dic[t]):
      if i == 0:
          ans.append((n, 1))
      else:
          etc.append((n, 0))
ans_all = calc_ans(ans)
ans.sort(reverse=True)
etc.sort(reverse=True)
for n in etc:
    #if ans[-1][1] == 0 and ans[-1][0] >= n[0]:
    #    break
    ans[-1] = n
    tmp = calc_ans(ans)
    if ans_all < tmp:
        ans_all = tmp
    ans.sort(reverse=True)
print(ans_all)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
ans = []
etc = []
dic = {}
ind = {}
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
for t in dic.keys():
    dic[t].sort(reverse=True)
    for i,n in enumerate(dic[t]):
      if i == 0:
          ans.append((n, 1))
      else:
          etc.append((n, 0))
ans_all = calc_ans(ans)
ans.sort(reverse=True)
etc.sort(reverse=True)
for n in etc:
    if ans[-1][1] == 0 and ans[-1][0] >= n[0]:
        break
    ans[-1] = n
    tmp = calc_ans(ans)
    if ans_all < tmp:
        ans_all = tmp
    ans.sort(reverse=True)
print(ans_all)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
ans = []
etc = []
dic = {}
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
for t in dic.keys():
    dic[t].sort(reverse=True)
    for i,n in enumerate(dic[t]):
      if i == 0:
          ans.append((n, 1))
      else:
          etc.append((n, 0))
ans_all = calc_ans(ans)
ans.sort(reverse=True)
for n in etc:
    ans[-1] = n
    tmp = calc_ans(ans)
    if ans_all < tmp:
        ans_all = tmp
    ans.sort(reverse=True)
print(ans_all)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

L = [list(map(int, input().split())) for i in range(N)]
L.sort(key=lambda x:x[1], reverse=True)
for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
    if len(dic.keys()) > K:
        break
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
all_ans = ans_res
for i, n in enumerate(etc):
    ans.sort(reverse=True)
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if all_ans < tmp_res:
        all_ans = tmp_res
    ans_res = tmp_res
print(all_ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
all_ans = ans_res
for i, n in enumerate(etc):
    ans.sort(reverse=True)
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if all_ans < tmp_res:
        all_ans = tmp_res
    ans_res = tmp_res
print(all_ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
all_ans = ans_res
for i, n in enumerate(etc):
    i+=1
    ans[-1*i] = n
    tmp_res = calc_ans(ans)
    if all_ans < tmp_res:
        all_ans = tmp_res
    ans_res = tmp_res
print(all_ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
all_ans = ans_res
for n in etc:
    ans.sort(reverse=True)
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if all_ans < tmp_res:
        all_ans = tmp_res
    ans_res = tmp_res
print(all_ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
ans_res = calc_ans(ans)
for n in etc:
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans_res = tmp_res
print(ans_res)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
ans_res = calc_ans(ans)
for n in etc:
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans_res = tmp_res
print(ans_res)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
ans_res = calc_ans(ans)
for n in etc:
    ans[-1] = n
    tmp_res = calc_ans(ans)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans_res = tmp_res
        ans.sorted(reverse=True)
print(ans_res)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
ans_res = calc_ans(ans)
for n in etc:
    tmp = copy.copy(ans)
    tmp[-1] = n
    tmp_res = calc_ans(tmp)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans = tmp
        ans_res = tmp_res
print(ans_res)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
ans_res = calc_ans(ans)
for n in etc:
    tmp = copy.copy(ans)
    tmp[-1] = n
    tmp_res = calc_ans(tmp)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans = tmp
        ans_res = tmp_res
print(tmp_res)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    return tmp + (x * x)

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
if N <= K:
    ans = 0
    for i in dic.keys():
        ans += sum(dic[i])
    ans += len(dic.keys()) * len(dic.keys())
    print(ans)
    exit()
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
for n in etc:
    ans_res = calc_ans(ans)
    tmp = copy.copy(ans)
    tmp[-1] = n
    tmp_res = calc_ans(tmp)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans = copy.copy(tmp)
print(tmp_res)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    tmp += x * x
    return tmp

for i in range(N):
    l = list(map(int, input().split()))
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n <= uniq[K-1][0]:
          break
      etc.append((n, 0))
etc.sort(reverse=True)
for n in etc:
    ans_res = calc_ans(ans)
    tmp = copy.copy(ans)
    tmp[-1] = n
    tmp_res = calc_ans(tmp)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans = copy.copy(tmp)
print(tmp_res)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
L = [list(map(int, input().split())) for i in range(N)]
dic = {}
ans = []
uniq = []
etc = []
def calc_ans(ans):
    x = 0
    tmp = 0
    for i in range(K):
      tmp += ans[i][0]
      x += ans[i][1]
    tmp += x * x
    return tmp

for l in L:
    if dic.get(l[0]):
        dic[l[0]].append(l[1])
    else:
        dic[l[0]] = [l[1]]
for t in dic.keys():
    dic[t].sort(reverse=True)
    uniq.append((dic[t][0], t))
uniq.sort(reverse=True)
for i in range(K):
  ans.append((uniq[i][0], 1))
  for n in dic[uniq[i][1]][1:]:
      if n > uniq[K-1][0]:
          etc.append((n, 0))
etc.sort(reverse=True)
for n in etc:
    ans_res = calc_ans(ans)
    tmp = copy.copy(ans)
    tmp[-1] = n
    tmp_res = calc_ans(tmp)
    if ans_res > tmp_res:
        print(ans_res)
        exit()
    else:
        ans = copy.copy(tmp)
print(tmp_res)

Submission status: Runtime Error

Solution code:

def read_input1():
    n, k = map(int, input().split())

    data_tuples = []
    for i in range(n):
        data_tuples.append(tuple(map(int, input().split())))

    return n, k, data_tuples


def count_neta(sushi_set):
    neta = {s[0] for s in sushi_set}
    return len(neta)


def sum_oishisa(sushi_set):
    oishisa = [s[1] for s in sushi_set]
    return sum(oishisa)


def check_value(sushi_set):
    neta_count = count_neta(sushi_set)
    oishisa = sum_oishisa(sushi_set)

    return oishisa + (neta_count * neta_count)


# ネタ数を減らさず、かつもっともおいしさの減少が少ないすしを探す
def check_changable_sushi(sushi_set):
    neta_count = count_neta(sushi_set)

    target = None
    for s in sushi_set:
        temp_sushi_set = sushi_set.remove(s)
        temp_neta_count = count_neta(temp_sushi_set)

        if neta_count == temp_neta_count:
            if target is None or target[1] > s[1]:
                target = s

        temp_sushi_set.append(s)
    return target


def find_other_sushi(all_sushi_set, sushi_set):
    neta_eaten = [s[0] for s in sushi_set]
    candidate_sushi = [sushi for sushi in all_sushi_set if sushi[0] not in neta_eaten]

    if candidate_sushi:
        target = max(candidate_sushi, key=lambda x: x[1])
    else:
        target = None

    return target


def next_neta_variation(all_sushi_set, sushi_set):
    drop_target = check_changable_sushi(sushi_set)
    if drop_target:
        insert_target = find_other_sushi(all_sushi_set, sushi_set)

        if insert_target:
            new_set = sushi_set.copy()
            new_set.remove(drop_target)
            new_set.append(insert_target)
            return new_set
    return None


if __name__ == '__main__':
    n, k, sushis = read_input1()
    neta_candidate = {}

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

    init_sushi_set = sushis[:k].copy()
    neta_count = count_neta(init_sushi_set)
    neta_candidate[neta_count] = init_sushi_set

    curr_sushi_set = init_sushi_set
    while True:
        next_sushi_set = next_neta_variation(sushis, curr_sushi_set)
        if not next_sushi_set:
            break

        curr_sushi_set = next_sushi_set
        neta_count = count_neta(curr_sushi_set)
        neta_candidate[neta_count] = curr_sushi_set

    max_score = -1
    for sushis in neta_candidate.values():
        score = check_value(sushis)
        if max_score < score:
            max_score = score

    print(max_score)

Submission status: Runtime Error

Solution code:
import math


def read_input1():
    n, k = map(int, input().split())

    data_tuples = []
    for i in range(n):
        data_tuples.append(tuple(map(int, input().split())))

    return n, k, data_tuples


def count_neta(sushi_set):
    neta = {s[0] for s in sushi_set}
    return len(neta)


def sum_oishisa(sushi_set):
    oishisa = [s[1] for s in sushi_set]
    return sum(oishisa)


def check_value(sushi_set):
    neta_count = count_neta(sushi_set)
    oishisa = sum_oishisa(sushi_set)

    return oishisa + (neta_count * neta_count)


# ネタ数を減らさず、かつもっともおいしさの減少が少ないすしを探す
def check_changable_sushi(sushi_set):
    neta_count = count_neta(sushi_set)

    target = None
    for s in sushi_set:
        temp_sushi_set = [sushi for sushi in sushi_set if sushi != s]
        temp_neta_count = count_neta(temp_sushi_set)

        if neta_count == temp_neta_count:
            if target is None or target[1] > s[1]:
                target = s

    return target


def find_other_sushi(all_sushi_set, sushi_set):
    candidate_sushi = [sushi for sushi in all_sushi_set if sushi not in sushi_set]
    neta_eaten = [s[0] for s in sushi_set]
    candidate_sushi = [s for s in candidate_sushi if s[0] not in neta_eaten]
    if candidate_sushi:
        target = max(candidate_sushi, key=lambda x: x[1])
    else:
        target = None

    return target


def next_neta_variation(all_sushi_set, sushi_set):
    drop_target = check_changable_sushi(sushi_set)
    if drop_target:
        insert_target = find_other_sushi(all_sushi_set, sushi_set)

        if insert_target:
            new_set = sushi_set.copy()
            new_set.remove(drop_target)
            new_set.append(insert_target)
            return new_set
    return None


if __name__ == '__main__':
    n, k, sushis = read_input1()
    neta_candidate = {}

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

    init_sushi_set = sushis[:k].copy()
    neta_count = count_neta(init_sushi_set)
    neta_candidate[neta_count] = init_sushi_set

    curr_sushi_set = init_sushi_set
    while True:
        next_sushi_set = next_neta_variation(sushis, curr_sushi_set)
        if not next_sushi_set:
            break

        curr_sushi_set = next_sushi_set
        neta_count = count_neta(curr_sushi_set)
        neta_candidate[neta_count] = curr_sushi_set


    max = -math.inf
    for sushis in neta_candidate.values():
        score = check_value(sushis)
        if max < score:
            max = score

    print(max)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def popMaxOishisa(sushis):
    t, d = sushis.pop()
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    t, d = -1, -1
    while True:
        t, d = sushis.pop()
        if not t in netas:
            break
    return t, d


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

# Store data
sushis = []
neta_set = set()
sel_sushis = {"min":{}}
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis[t].append(d)
        if sel_sushis["min"][t] > d:
            sel_sushis["min"][t] = d
    sum_oishisa += d

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    if t1 < 0:
        break
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)