Problem:


Score : 400 points

Problem Statement

There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i.
You are choosing K among these N pieces to eat.
Your "satisfaction" here will be calculated as follows:

The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".

The base total deliciousness is the sum of the deliciousness of the pieces you eat.

The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.

You want to have as much satisfaction as possible.
Find this maximum satisfaction.

Constraints

1 \leq K \leq N  \leq 10^5

1 \leq t_i \leq N

1 \leq d_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

Output

Print the maximum satisfaction that you can obtain.

Sample Input 1

5 3
1 9
1 7
2 6
2 5
3 1

Sample Output 1

26

If you eat Sushi 1,2 and 3:

The base total deliciousness is 9+7+6=22.

The variety bonus is 2*2=4.

Thus, your satisfaction will be 26, which is optimal.

Sample Input 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

Sample Output 2

25

It is optimal to eat Sushi 1,2,3 and 4.

Sample Input 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

Sample Output 3

4900000016

Note that the output may not fit into a 32-bit integer type.



Sample input:
5 3
1 9
1 7
2 6
2 5
3 1


Sample output:
26

Submission status: Time Limit Exceeded

Solution code:
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
t, d = [], []


for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))


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

def SumScore(List, K):
    taste = 0
    kind = []
    for i in range(K):
        taste += List[i][1]
        kind.append(List[i][0])
    return taste + len(set(kind))**2

def SearchNew(List, K):
    kind = []
    newkind = -1
    for i in range(K):
        kind.append(List[i][0])
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K):
    result = -1
    leftkind = []
    for j in range(K):
        leftkind.append(List[j][0])
    for i in range(K):
        testkind = List[K-1-i][0]
        leftkind.pop(K-1-i)
        if testkind in leftkind:
            result = K-1-i
            break
    return result

Score = SumScore(Parameters, K)

for t in Parameters:
    i = SearchNew(Parameters, K)
    j = SearchDouble(Parameters, K)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    Test = SumScore(Parameters, K)
    if Score <= Test:
        Score = Test

print(Score)

Submission status: Time Limit Exceeded

Solution code:
#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0


for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

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

def SumScore(List, K):
    taste = 0
    kind = []
    for i in range(K):
        taste += List[i][1]
        kind.append(List[i][0])
    return taste + len(set(kind))**2

def SearchNew(List, K):
    kind = []
    newkind = -1
    for i in range(K):
        kind.append(List[i][0])
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K):
    result = -1
    for i in range(K):
        leftkind = []
        for j in range(K):
            leftkind.append(List[j][0])
        testkind = List[K-1-i][0]
        leftkind.pop(K-1-i)
        if testkind in leftkind:
            result = K-1-i
            break
    return result

Score = SumScore(Parameters, K)

for t in Parameters:
    i = SearchNew(Parameters, K)
    j = SearchDouble(Parameters, K)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    Test = SumScore(Parameters, K)
    if Score <= Test:
        Score = Test

print(Score)

Submission status: Time Limit Exceeded

Solution code:
def seek_dup(s):
    t_list = [t for (t, d) in s]
    #d_list = [d for (t, d) in s]
 
    for t, d in reversed(s):
        if t_list.count(t) > 1:
            return (t, d)
        else:
            continue
        
    return None
 
N, K = map(int, input().split())
menu_ = []
 
for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))
 
menu = sorted(menu_, key = lambda x:x[1], reverse=True)
p = sum([d for (t, d) in menu[:K]]) + len(set([t for (t, d) in menu[:K]]))**2
 
selected_menu = menu[:K]
t_list = [t for (t, d) in selected_menu]
d_list = [d for (t, d) in selected_menu]
ans = p
for m in menu[K:]:
    
    if m[0] not in t_list:
        d = seek_dup(selected_menu)
        if d == None:
            continue
        
        selected_menu.remove(d)
        selected_menu.append(m)
        t_list = [t for (t, d) in selected_menu]
        d_list = [d for (t, d) in selected_menu]        
        
    
        p += (m[1] - d[1]) + 2 * len(set(t_list)) - 1 
        #print(ans, p)
        ans = max(ans, p)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
menu = {}

for i in range(N):
    t, d = map(int, input().split())
    menu[i] = (t, d)

def manzoku(s):
    manzoku = sum([menu[i][1] for i in s]) + len(set([menu[i][0] for i in s]))**2
    return manzoku

#K sushi
shushi = itertools.combinations(menu, K)
print(max([manzoku(c) for c in shushi]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
menu = {}

for i in range(N):
    t, d = map(int, input().split())
    menu[i] = (t, d)

def manzoku(s):
    #Oishisa basic point
    Oishisa = sum([menu[i][1] for i in s])
   
    #Syurui bonus point
    Syurui = len(set([menu[i][0] for i in s]))**2
    
    #Manzoku point
    return Oishisa + Syurui

#K sushi    
shushi = itertools.combinations(menu, K)
print(max([manzoku(c) for c in shushi]))

Submission status: Time Limit Exceeded

Solution code:
import collections

n, k = map(int, input().split())
h = []
for i in range(n):
    a, b = map(int, input().split())
    h.append((a,b))
h.sort(key=lambda x: -x[1])
fav=h[0:k]
tb={}
for t,d in sorted(h[k:], key=lambda x: (-x[0], -x[1])):
    tb[t] = tb.get(t, []) + [d]
alt = []
for t,ds in tb.items():
    alt.append((t,max(ds)))
alt.sort(key=lambda x: -x[1])

# print("h: ",h)
# print("fav: ",fav)
# print("alt: ",alt)


var = len(set([x[0] for x in fav]))

bestscore = var**2 + sum([x[1] for x in fav])

while(len(alt) > 0):
    c = collections.Counter([x[0] for x in fav])
    temp = sorted(filter(lambda x: c[x[0]] > 1, fav), key=lambda x: -x[1])
    if(len(temp) == 0):
        break
    while(len(alt) > 0):
        t1, d1 = alt.pop(0)
        if(c[t1] == 0):
            break
    if(c[t1] != 0):
        break
    t2, d2 = temp[-1]


    fav.remove((t2,d2))
    fav.append((t1, d1))
    var += 1

    bestscore = max(bestscore, var**2 + sum([x[1] for x in fav]))

    # print("fav: ",fav)
    # print("alt: ",alt)

print(bestscore)

Submission status: Time Limit Exceeded

Solution code:
def get_point(l):
  deli = 0
  kind = set()
  for x in l:
    kind = kind | set([x[0]])
    deli += x[1]
  
  point = deli + len(kind) * len(kind)
  return point, kind


def remove_deplicated_kind(l, kind):
  l = [[x[0], x[1]] for x in l if x[0] not in kind]
  return l


def replace_data(curr, rest):
  alt = [rest[0]] + curr[:-1]
  replaced = curr[-1]
  _, kind1 = get_point(curr)
  _, kind2 = get_point(alt)
  
  i = 0
  while len(kind1) >= len(kind2):
    temp = [replaced] + alt[:-1]
    replaced = alt[-1]
    alt = temp
    _, kind2 = get_point(alt)
    i += 1
    if i >= len(curr):
      break
  
  return alt


n, k = map(int, input().split())
l = []
for _ in range(n):
  t, d = map(int, input().split())
  l.append([t, d])

l = sorted(l, key=lambda x: -x[1])
curr = l[:k]
rest = l[k:]

p, kind1 = get_point(curr)
ans = [p]

while len(rest) > 0:
  curr = replace_data(curr, rest)
  p, kind = get_point(curr)
  rest = rest[1:]
  rest = remove_deplicated_kind(rest, kind)
  ans.append(p)

print(max(ans))

Submission status: Time Limit Exceeded

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

td=sorted([tuple(map(int,input().split())) for _ in range(N)],key=lambda x:-x[1])
answer=0
number=[]
afterpop=[]

for i in range(K):
  answer+=td[i][1]
  if td[i][0] not in number:
    number.append(td[i][0])
  else:
    afterpop.append(td[i][1])

answer+=len(number)**2
    
index=K
tempanswer=answer
while index<N and afterpop:
  if td[index][0] not in number:
    number.append(td[index][0])
    tempanswer=tempanswer+td[index][1]-afterpop.pop()-(len(number)-1)**2+(len(number))**2
    answer=max(tempanswer,answer)
  index+=1
                  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools

nklist = list(map(int,input().split()))
n, k= nklist[0], nklist[1]

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

max_pt = 0
for comb in itertools.combinations(lst, k):
    kinds_set = set()
    umami = 0
    for tpl in comb:
        kinds_set.add(tpl[0])
        umami += tpl[1]
    ttl_pt = len(kinds_set)**2 + umami
    if ttl_pt > max_pt:
        max_pt = ttl_pt
print(max_pt)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

li2 = list(itertools.permutations(li, k))
max_score = 0
for i in range(len(li2)):
  li3 = li2[i]
  sushi_set = set()
  taste = 0
  for j in range(len(li3)):
    sushi_set.add(li3[j][0])
    taste += li3[j][1]

  max_score = max(max_score, taste + len(sushi_set) ** 2) 

print(max_score)

Submission status: Time Limit Exceeded

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

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

ans=0
eat=[]
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.append(t)
  else:
    noteat.append(d)
temp_result=ans+len(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.append(t)
    max_result=max(max_result,temp_result)
print(max_result)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

N,K = inpl()
ans = 0
n0 = []
n1 = {}
neta = set()

for _ in range(N):
    ti,di = inpl()
    if(ti in neta):
        if(n1[ti]<di):
            n0.append(n1[ti])
            n1[ti] = di
        else:
            n0.append(di)
    else:
        n1[ti] = di
        neta.add(ti)

n1 = list(n1.values())
n0.sort(reverse = True)
n1.sort(reverse = True)

for i in range(min(K+1,len(n1)+1)):
    if(K-i <= len(n0) and 0<=K-i):
        total = sum(n1[:i]+n0[:K-i])+i*i
        if(ans<total):
            ans = total

print(ans)

Submission status: Time Limit Exceeded

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:
        sushi_set.remove(s)
        temp_neta_count = count_neta(sushi_set)

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

        sushi_set.append(s)
    return target


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

    target = None
    for sushi in all_sushi_set:
        if sushi[0] not in neta_eaten:
            if target is None or target[1] < sushi[1]:
                target = sushi

    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:
            sushi_set.remove(drop_target)
            sushi_set.append(insert_target)
            return sushi_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]
    neta_count = count_neta(init_sushi_set)
    neta_candidate[neta_count] = check_value(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] = check_value(curr_sushi_set)

        if neta_count == k:
            break

    print(max(neta_candidate.values()))

Submission status: Time Limit Exceeded

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:
        sushi_set.remove(s)
        temp_neta_count = count_neta(sushi_set)

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

        sushi_set.append(s)
    return target


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

    target = None
    for sushi in all_sushi_set:
        if sushi[0] not in neta_eaten:
            if target is None or target[1] < sushi[1]:
                target = sushi

    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

        if neta_count == k:
            break

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

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:
        sushi_set.remove(s)
        temp_neta_count = count_neta(sushi_set)

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

        sushi_set.append(s)
    return target


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

    target = None
    for sushi in all_sushi_set:
        if sushi[0] not in neta_eaten:
            if target is None or target[1] < sushi[1]:
                target = sushi

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

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 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_score = -1
    for sushis in neta_candidate.values():
        score = check_value(sushis)
        if max_score < score:
            max_score = score

    print(max_score)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

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

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k:][i-1])

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])
    tl, dl = zip(*sl)

    gmk = set()
    ce = []
    for s in sl[:k]:
        if s[0] in gmk:
            ce.append(s)
        gmk.add(s[0])

    gop = sum(dl[:k])
    bmk = max(len(set(tl)), k)

    gscr = len(gmk)**2 + gop

    ce.sort(key=lambda x: x[1])
    for c in ce[:bmk-len(gmk)]:
        for s in sl[k:]:
            if s[0] in gmk:
                continue
            k += 1
            gmk.add(s[0])
            gop = gop - c[1] + s[1]
            nscr = len(gmk)**2 + gop
            gscr = max(gscr, nscr)
            break

    return gscr


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])
    tl, dl = zip(*sl)

    gmk = set()
    ce = []
    for s in sl[:k]:
        if s[0] in gmk:
            ce.append(s)
        gmk.add(s[0])

    gop = sum(dl[:k])
    bmk = max(len(set(tl)), k)

    gscr = len(gmk)**2 + gop

    ce.sort(key=lambda x: x[1])
    for c in ce[:bmk-len(gmk)]:
        for s in sl[k:]:
            if s[0] in gmk:
                continue
            k += 1
            gmk.add(s[0])
            gop = gop - c[1] + s[1]
            nscr = len(gmk)**2 + gop
            gscr = max(gscr, nscr)
            break

    return gscr


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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


def popMinOishisa_nonUniqueNeta(sel_sushis):
    if len(sel_sushis["min"]) == 0:
        return -1, -1
    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"].pop(t)
    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 = {}
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]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}
sel_neta = list(sel_sushis.keys())

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, sel_neta)
    sum_oishisa += d2

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

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

print(max_score)

Submission status: Time Limit Exceeded

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])
    if d > 1e9:
        return -1, -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)

Submission status: Time Limit Exceeded

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

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


def popMinOishisa_nonUniqueNeta(sel_sushis):
    if len(sel_sushis["min"]) == 0:
        return -1, -1
    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"].pop(t)
    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 = {}
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]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}

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)

Submission status: Time Limit Exceeded

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

def popMaxOishisa(sushis):
    t, d = max(sushis["max"].items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    if len(sel_sushis["min"]) == 0:
        return -1, -1
    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"].pop(t)
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    max_dict = {k:v for k,v in sushis["max"].items() if not k in netas}
    t, d = max(max_dict.items(), key=lambda i:i[1])
    if len(sushis[t]) == 1:
        sushis.pop(t)
        sushis["max"].pop(t)
    else:
        sushis[t].pop()
        sushis["max"][t] = sushis[t][-1]
    return t, d


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

# Store data
sushis = {}
sel_sushis = {}
for i in range(n):
    t, d = map(int, input().split())
    if not t in sushis:
        sushis[t] = [d]
    else:
        sushis[t].append(d)

# Formatting
for type in sushis:
    sushis[type].sort()
sushis["max"] = {t:sushis[t][-1] for t in sushis}

tMax = len(sushis) - 1

# 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]
    else:
        sel_sushis[t].append(d)
    sum_oishisa += d
sel_sushis["min"] = {t:sel_sushis[t][-1] for t in sel_sushis if len(sel_sushis[t]) > 1}

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 t1 in sushis:
        sushis[t1] = [d1]
    else:
        sushis[t1].append(d1)

    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)