Problem p03148 (python)

Fixed submission:
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]

###dが大きい順にソート
td.sort(key = lambda x: x[1],reverse=True)

###各tでdが最大のものを格納
fix_eated_d=[]
###各tでdが最大でないものを格納。tの種類を増やす際の削除候補
change_eated_d=[]

eated_t = set()
d_point = 0

###まずdを最大化
for t,d in td[:k]:
  
  ###すでにtが選ばれているなら最大のdではないのでchangeへ
  if t in eated_t:
    change_eated_d.append(d)
    
  ###まだtが選ばれていないなら最大のdだからfixへ
  else:
    fix_eated_d.append(d)
    eated_t.add(t)
    
  d_point += d
  
point = len(eated_t)**2 + d_point

###tの種類を増やす
for t,d in td[k:]:
  ###削除候補がなくなれば終了
  if not change_eated_d:
    break
  
  ###すでにtが選ばれているならskip
  if t in eated_t:
    continue
    
  ###まだtが選ばれていないなら追加、change中dが最小のものを削除
  eated_t.add(t)
  d_point += d - change_eated_d.pop()
  point = max(point, len(eated_t)**2 + d_point)
  
print(point)

Buggy submission (verdict: Runtime Error):
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]

###dが大きい順にソート
td.sort(key = lambda x: x[1],reverse=True)

###各tでdが最大のものを格納
fix_eated_d=[]
###各tでdが最大でないものを格納。tの種類を増やす際の削除候補
change_eated_d=[]

eated_t = set()
d_point = 0

###まずdを最大化
for t,d in td[:k]:
  ###すでにtが選ばれているなら最大のdではないのでchangeへ
  if t in eated_t:
    change_eated_d.append(d)
    
  ###まだtが選ばれていないなら最大のdだからfixへ
  else:
    fix_eated_d.append(d)
    eated_t.add(t)
  d_point += d
point = len(eated_t)**2 + d_point

###tの種類を増やす
for t,d in td[k:]:
  ###すでにtが選ばれているならskip
  if t in eated_t:
    continue
    
  ###まだtが選ばれていないなら追加、change中dが最小のものを削除
  eated_t.add(t)
  d_point += d - change_eated_d.pop()
  point = max(point, len(eated_t)**2 + d_point)
  
  ###削除候補がなくなれば終了
  if not change_eated_d:
    break
  
print(point)

Buggy submission (verdict: Runtime Error):
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]

###dが大きい順にソート
td.sort(key = lambda x: x[0],reverse=True)
td.sort(key = lambda x: x[1],reverse=True)

###なるべくtの種類を多いなかで、dを最大化する
###まず各tでdが最大のものを1つずつ選ぶ
eated_kind = []
eated_kind_num = 0
eated = []
for t,d in td:
  if t not in eated_kind:
    eated_kind.append(t)
    eated_kind_num += 1
    eated.append([t,d])
    
    ###tがk種類存在したら、残りのtを扱うことはない
    ###またdも最大化されているため、これ以降のtdを使うことはない
    if eated_kind_num == k:
      td = td[:i+1]
      break

not_eated = [i for i in td if i not in eated]

###tがk種類存在しなかったら、k個になるまでtに関係なくdを最大化する
if eated_kind_num < k:
  eated += not_eated[:k-eated_kind_num]
  not_eated = not_eated[k-eated_kind_num:]
  #print(eated)
  eated.sort(key = lambda x: x[1],reverse=True)
  
t_point = eated_kind_num**2
d_point = sum([i[1] for i in eated])
point = t_point + d_point
###種類の寿司でdの最大化をする
for t,d in not_eated:
  eated_last_t, eated_last_d = eated[-1]
  t_point_sub = (eated_kind_num-1)**2 - eated_kind_num**2
  d_point_sub = d - eated_last_d
  eated = eated[:-1]
  point = max(point,point+t_point_sub+d_point_sub)
  eated_kind_num -= 1
  if eated_kind_num == 1:
    break
#print(eated)

print(point)

Buggy submission (verdict: Runtime Error):
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]

###dが大きい順にソート
td.sort(key = lambda x: x[0],reverse=True)
td.sort(key = lambda x: x[1],reverse=True)

###なるべくtの種類を多いなかで、dを最大化する
###まず各tでdが最大のものを1つずつ選ぶ
eated_kind = []
eated_kind_num = 0
eated = []
for t,d in td:
  if t not in eated_kind:
    eated_kind.append(t)
    eated_kind_num += 1
    eated.append([t,d])
    
    ###tがk種類存在したら、残りのtを扱うことはない
    ###またdも最大化されているため、これ以降のtdを使うことはない
    if eated_kind_num == k:
      td = td[:i+1]
      break

not_eated = [i for i in td if i not in eated]

###tがk種類存在しなかったら、k個になるまでtに関係なくdを最大化する
if eated_kind_num < k:
  eated += not_eated[:k-eated_kind_num]
  not_eated = not_eated[k-eated_kind_num:]
  #print(eated)
  eated.sort(key = lambda x: x[1],reverse=True)
  
t_point = eated_kind_num**2
d_point = sum([i[1] for i in eated])
point = t_point + d_point
###種類の寿司でdの最大化をする
for t,d in not_eated:
  eated_last_t, eated_last_d = eated[-1]
  t_point_sub = (eated_kind_num-1)**2 - eated_kind_num**2
  d_point_sub = d - eated_last_d
  eated = eated[:-1]
  point = max(point,point[-1]+t_point_sub+d_point_sub)
  eated_kind_num -= 1    
#print(eated)

print(point)

Buggy submission (verdict: Runtime Error):
n,k = [int(i) for i in input().split()]
td = [[int(i) for i in input().split()] for _ in range(n)]

###dが大きい順にソート
td.sort(key = lambda x: x[1],reverse=True)

###なるべくtの種類を多いなかで、dを最大化する
###まず各tでdが最大のものを1つずつ選ぶ
eated_kind = []
eated = []
for i in range(n):
  t,d = td[i]
  if t not in eated_kind:
    eated_kind.append(t)
    eated.append([t,d])
    
    ###tがk種類存在したら、残りのtを扱うことはない
    ###またdも最大化されているため、これ以降のtdを使うことはない
    if len(eated_kind) == k:
      td = td[:i+1]
      break

eated_kind_num = len(eated_kind)
not_eated = [i for i in td if i not in eated]

###tがk種類存在しなかったら、k個になるまでtに関係なくdを最大化する
if eated_kind_num < k:
  eated.append(not_eated[:k-cnt])
  not_eated = not_eated[k-cnt:]
  eated.sort(key = lambda x: x[1],reverse=True)
  
###dの最大化を目指すが、tの種類が減る場合どちらのほうが良いか判断する必要がある
for t,d in not_eated:
  eated_last_t, eated_last_d = eated[-1]
  if d < eated_last_d:
    break
  t_point_sub = (eated_kind_num-1)**2 - eated_kind_num**2
  d_point_sub = d - eated_last_d
  if t_point_sub + d_point_sub > 0:
    eated = [[t,d]] + eated[:-1]
    eated_kind_num -= 1
  else:
    break
    
#print(eated)

t_point = eated_kind_num**2
d_point = sum([i[1] for i in eated])
point = t_point + d_point
print(point)