Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02805 (python)

Fixed submission:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
sgm=pow(10,-7)
def func(c):
    allp=[]
    for i in range(n-1):
        for j in range(i+1,n):
            xi,yi=xy[i]
            xj,yj=xy[j]
            dx=xi-xj
            dy=yi-yj
            d=((xi-xj)**2+(yi-yj)**2)**0.5
            if c**2-(d/2)**2<0:return False
            h=(c**2-(d/2)**2)**0.5
            mx,my=(xi+xj)/2,(yi+yj)/2
            if dx==0:
                allp.append([mx-h,my])
                allp.append([mx+h,my])
            elif dy==0:
                allp.append([mx,my-h])
                allp.append([mx,my+h])
            else:
                dx,dy=dy,-dx
                dh=(dy**2+dx**2)**0.5
                dx*=h/dh
                dy*=h/dh
                allp.append([mx+dx,my+dy])
                allp.append([mx-dx,my-dy])
    for px,py in allp:
        flg=True
        for x,y in xy:
            if ((px-x)**2+(py-y)**2)**0.5>c+sgm:
                flg=False
                break
        if flg:
            return True
    return False

r=2*max([abs(x) for x,y in xy])+max([abs(y) for x,y in xy])
l,r=0,r
for i in range(400):
    c=(l+r)/2
    if func(c):
        l,r=l,c
    else:
        l,r=c,r
print(c)
#print(c**2)

Buggy submission (verdict: Runtime Error):
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
sgm=pow(10.-7)
def func(c):
    allp=[]
    for i in range(n-1):
        for j in range(i+1,n):
            xi,yi=xy[i]
            xj,yj=xy[j]
            dx=xi-xj
            dy=yi-yj
            d=((xi-xj)**2+(yi-yj)**2)**0.5
            if c**2-(d/2)**2<0:return False
            h=(c**2-(d/2)**2)**0.5
            mx,my=(xi+xj)/2,(yi+yj)/2
            if dx==0:
                allp.append([mx-h,my])
                allp.append([mx+h,my])
            elif dy==0:
                allp.append([mx,my-h])
                allp.append([mx,my+h])
            else:
                dx,dy=dy,-dx
                dh=(dy**2+dx**2)**0.5
                dx*=h/dh
                dy*=h/dh
                allp.append([mx+dx,my+dy])
                allp.append([mx-dx,my-dy])
    for px,py in allp:
        flg=True
        for x,y in xy:
            if ((px-x)**2+(py-y)**2)**0.5>c+sgm:
                flg=False
                break
        if flg:
            return True
    return False

r=2*max([abs(x) for x,y in xy])+max([abs(y) for x,y in xy])
l,r=0,r
for i in range(300):
    c=(l+r)/2
    if func(c):
        l,r=l,c
    else:
        l,r=c,r
print(c)
#print(c**2)
Problem p02838 (python)

Fixed submission:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  ans=0
  bit=[0]*61 #bit[i]:2^iの位が1である物の個数
  for ai in a:
    for j in range(61):
      if ((ai>>j) & 1):
        bit[j]+=1
  for i in range(61):
    ans+=(pow(2,i)%mod)*bit[i]*(n-bit[i])
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  #a=list(map(lambda x:list(map(int,list(bin(int(x))[2:]))),input().split()))
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  bit=[]
  for ai in a:
    for j in range(61):
      if ((ai>>j)&1):
        bit[j]+=1
  for i in range(61):# 2^iの位
    ans+=(pow(2,i,mod)*bit[i]*(n-bit[i]))%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,lambda x:list(map(int,list(bin(int(x))[2:]))),input().split()))
  mod=pow(10,9)+7
  ans=0
  len_ai=[]
  for ai in a:
    len_ai.append(len(ai))
  for i in range(61):# 2^iの位
    bit1=0
    for j in range(n):
      if len_ai[j]>=i+1:
        bit1+=a[j][-i-1]
    ans+=(pow(2,i,mod)*bit1*(n-bit1))%mod
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
Problem p02845 (python)

Fixed submission:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  dp=[0,0,0] # dp[j]:前から順番に見た時の帽子jの数
  ans=1
  for ai in a:
    if ai in dp:
      ans*=dp.count(ai)
      ans%=mod
      dp[dp.index(ai)]+=1
    else:
      print(0)
      exit()
  print(ans)
if __name__=='__main__':
  main()

Buggy submission (verdict: Runtime Error):
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  dp=[0,0,0] # dp[j]:前から順番に見た時の帽子jの数
  ans=1
  for ai in a:
    ans*=dp.count(ai)
    ans%=mod
    dp[dp.index(ai)]+=1
  print(ans)

if __name__=='__main__':
  main()
Problem p02866 (python)

Fixed submission:
from collections import defaultdict
n=int(input())
d=list(map(int,input().split()))
mod=998244353
if d[0]!=0:
      print(0)
      exit()
dd=defaultdict(lambda:0)
for di in d:
      dd[di]+=1
if dd[0]>1:
      print(0)
      exit()
ans=1
for i in set(dd.keys()):
      if i==0:
            continue
      ans*=(dd[i-1]**dd[i])%mod
print(ans%mod)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
n=int(input())
d=list(map(int,input().split()))
mod=998244353
if d[0]!=0:
      print(0)
      exit()
dd=defaultdict(lambda:0)
for di in d:
      dd[di]+=1
if dd[0]>1:
      print(0)
      exit()
ans=1
for i in dd.keys():
      if i==0:
            continue
      ans*=(dd[i-1]**dd[i])%mod
print(ans%mod)
Problem p02874 (python)

Fixed submission:
n=int(input())
lr=[list(map(int,input().split())) for _ in range(n)]
lr.sort(key=lambda x:x[0])
# 右端がもっとも左にある問題
r0=0
tmpr=float('inf')
# 左端がもっとも右にある問題
l0=0
tmpl=0
for i,x in enumerate(lr):
  l,r=x
  if tmpl<l:
    l0=i
    tmpl=l
  if tmpr>r:
    r0=i
    tmpr=r
if l0==r0:
  ans=lr[r0][1]-lr[l0][0]+1
  tmp=0
  for i in range(n):
    if i==l0:continue
    l,r=lr[i]
    tmp=max(tmp,r-l+1)
  ans+=tmp
  print(ans)
  exit()
ans0=max(0,lr[r0][1]-lr[l0][0]+1)
tmp=0
for i in range(n):
  if i==l0 or i==r0:continue
  l,r=lr[i]
  tmp=max(tmp,r-l+1)
ans0+=tmp


import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()
  def insert(self,x):
    heapq.heappush(self.p, x)
    return
  def erase(self,x):
    heapq.heappush(self.q, x)
    return
  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else None
pq=pqheap()

[pq.insert(x[1]) for i,x in enumerate(lr) if i!=l0 and i!=r0]
l1,r1=lr[r0]
l2,r2=lr[l0]
if pq.minimum():r2=min(r2,pq.minimum())
ans1=max(r1-l1+1,0)
ans1+=max(r2-l2+1,0)
for i,[l,r] in enumerate(lr):
  if i==l0 or i==r0:continue
  tmp=0
  l1=max(l1,l)
  pq.erase(r)
  tmp=max(r1-l1+1,0)
  if pq.minimum():
    r2=min(lr[l0][1],pq.minimum())
  else:
    l2,r2=lr[l0]
  tmp+=max(r2-l2+1,0)
  ans1=max(ans1,tmp)
print(max(ans1,ans0))

Buggy submission (verdict: Runtime Error):
n=int(input())
lr=[list(map(int,input().split())) for _ in range(n)]
lr.sort(key=lambda x:x[0])
# 右端がもっとも左にある問題
r0=0
tmpr=float('inf')
# 左端がもっとも右にある問題
l0=0
tmpl=0
for i,x in enumerate(lr):
  l,r=x
  if tmpl<l:
    l0=i
    tmpl=l
  if tmpr>r:
    r0=i
    tmpr=r
if l0==r0:
  ans=lr[r0][1]-lr[l0][0]+1
  tmp=0
  for i in range(n):
    if i==l0:continue
    l,r=lr[i]
    tmp=max(tmp,r-l+1)
  ans+=tmp
  print(ans)
  exit()
ans0=max(0,lr[r0][1]-lr[l0][0]+1)
tmp=0
for i in range(n):
  if i==l0 or i==r0:continue
  l,r=lr[i]
  tmp=max(tmp,r-l+1)
ans0+=tmp


import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()
  def insert(self,x):
    heapq.heappush(self.p, x)
    return
  def erase(self,x):
    heapq.heappush(self.q, x)
    return
  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else None
pq=pqheap()

[pq.insert(x[1]) for i,x in enumerate(lr) if i!=l0 and i!=r0]
l1,r1=lr[r0]
l2,r2=lr[l0]
r2=min(r2,pq.minimum())
ans1=max(r1-l1+1,0)
ans1+=max(r2-l2+1,0)
for i,[l,r] in enumerate(lr):
  if i==l0 or i==r0:continue
  tmp=0
  l1=max(l1,l)
  pq.erase(r)
  tmp=max(r1-l1+1,0)
  if pq.minimum():
    r2=min(lr[l0][1],pq.minimum())
  else:
    l2,r2=lr[l0]
  tmp+=max(r2-l2+1,0)
  ans1=max(ans1,tmp)
print(max(ans1,ans0))
Problem p02936 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def main():
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
    px=[list(map(int,input().split())) for _ in range(q)]
    seen=[0]*(n+1)
    ans=[0]*(n+1)
    for p,x in px:
        ans[p]+=x
    def dfs(i):
        seen[i]=1
        for li in graph[i]:
            if seen[li]==0:
                ans[li]+=ans[i]
                dfs(li)
    dfs(1)
    print(' '.join(map(str,ans[1:])))
if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main(n,ab,px):
  g=[[]for _ in range(n+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)
  ans=[0]*n
  for p,x in px:
    ans[p-1]+=x
  
  def dfs(seen,i):
    seen[i-1]=1
    l=g[i]
    for li in [li for li in l if seen[li-1]==0]:
      ans[li-1]+=ans[i-1]
      dfs(seen,li)
  seen=[0]*n
  dfs(seen,1)
  print(' '.join(list(map(str,ans))))

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n,q=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  px=[list(map(int,input().split())) for _ in range(q)]
  main(n,ab,px)

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
graph=[[] for _ in range(n+1)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
px=[list(map(int,input().split())) for _ in range(q)]
ans=[0]*(n+1)
for p,x in px:
    ans[p]+=x
seen=[0]*(n+1)
def dfs(i):
    seen[i]=1
    for li in graph[i]:
        if seen[li]==0:
            ans[li]+=ans[i]
            dfs(li)
dfs(1)
print(' '.join(map(str,ans[1:])))

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
graph=[[] for _ in range(n+1)]
ab=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
px=[list(map(int,input().split())) for _ in range(q)]
ans=[0]*(n+1)
for p,x in px:
    ans[p]+=x
seen=[0]*(n+1)
def dfs(i):
    seen[i]=1
    l=graph[i]
    for li in l:
        if seen[li]==0:
            ans[li]+=ans[i]
            todo.append(li)
    if len(todo)>0:
        dfs(todo.pop())
todo=[1]
dfs(todo.pop())
print(' '.join(map(str,ans[1:])))
Problem p02960 (python)

Fixed submission:
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Buggy submission (verdict: Runtime Error):
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=p_dp.copy()
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  main()
Problem p02975 (python)

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())))
if n%3==0:
  d={}
  for ai in a:
    if ai not in d:
      d[ai]=a.count(ai)
      if len(d)==4:
        break
  sa=list(set(a))
  if len(sa)==3 and sa[0]^sa[1]==sa[2] and d[sa[0]]==d[sa[1]] and d[sa[0]]==d[sa[2]]:
    print('Yes')
    exit()
  if len(sa)==2 and 0 in d and 2*d[0]==max(d[sa[0]],d[sa[1]]):
    print('Yes')
    exit()

if n == a.count(0):
  print('Yes')
  exit()

print('No')

Buggy submission (verdict: Runtime Error):
n=int(input())
a=sorted(list(map(int,input().split())))
if n%3==0:
  d={}
  for ai in a:
    if ai not in d:
      d[ai]=a.count(ai)
  sa=list(set(a))
  if sa[0]^sa[1]==sa[2] and d[sa[0]]==d[sa[1]] and d[sa[0]]==d[sa[2]]:
    print('Yes')
    exit()
print('No')

Buggy submission (verdict: Runtime Error):
an=int(input())
a=sorted(list(map(int,input().split())))
if n%3==0:
  d={}
  for ai in a:
    if ai not in d:
      d[ai]=a.count(ai)
  sa=list(set(a))
  if sa[0]^sa[1]==sa[2] and d[sa[0]]==d[sa[1]] and d[sa[0]]==d[sa[2]]:
    print('Yes')
    exit()
print('No')
Problem p02995 (python)

Fixed submission:
import math
import fractions
a,b,c,d=map(int,input().split())
base=b-a+1
n_c=b//c-(a+c-1)//c+1
n_d=b//d-(a+d-1)//d+1
cd=c*d//fractions.gcd(c,d)
n_cd=b//cd-(a+cd-1)//cd+1
print(base-n_c-n_d+n_cd)

Buggy submission (verdict: Runtime Error):
import math
a,b,c,d=map(int,input().split())
base=b-a+1

n_c=math.floor(b/c)-math.ceil(a/c)+1
n_d=math.floor(b/d)-math.ceil(a/d)+1
cd=c*d/math.gcd(c,d)
n_cd=math.floor(b/cd)-math.ceil(a/cd)+1
print(base-n_c-n_d+n_cd)
Problem p03006 (python)

Fixed submission:
from collections import defaultdict
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
if n==1:
  print(1)
  exit()
d=defaultdict(lambda:0)
for i in range(n-1):
  for j in range(i+1,n):
    dx=xy[i][0]-xy[j][0]
    dy=xy[i][1]-xy[j][1]
    d[(dx,dy)]+=1
    d[(-dx,-dy)]+=1
print(n-max(d.values()))
#for k,v in d.items():
#  print(k,v)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
d=defaultdict(lambda:0)
for i in range(n-1):
  for j in range(i+1,n):
    dx=xy[i][0]-xy[j][0]
    dy=xy[i][1]-xy[j][1]
    d[(dx,dy)]+=1
    d[(-dx,-dy)]+=1
print(n-max(d.values()))
Problem p03081 (python)

Fixed submission:
n,q=map(int,input().split())
s=input()
td=[list(input().split()) for _ in range(q)]
def func0(x):
  # はじめx(0-indexed)にいるゴーレムが0から左にいき消滅するか
  for t,d in td:
    if t==s[x]:
      if d=='R':x+=1
      if d=='L':x-=1
    if x<0:return True
    if x>n-1:return False
  return False
def funcN(x):
  # はじめx(0-indexed)にいるゴーレムがn-1から右にいき消滅するか
  for t,d in td:
    if t==s[x]:
      if d=='R':x+=1
      if d=='L':x-=1
    if x<0:return False
    if x>n-1:return True
  return False

l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if func0(x):
    l,r=x,r
  else:
    l,r=l,x
a=l
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if funcN(x):
    l,r=l,x
  else:
    l,r=x,r
b=r
print(n-(a+1)-(n-b))

Buggy submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
td=[list(input().split()) for _ in range(q)]


def bichk(x,flg):
  now=[x,s[x]]
  for t,d in td:
    if t==now[1]:
      if d=='L':
        x-=1
        if x<0 and flg:return False
        now=[x,s[x]]
      else:
        x+=1
        if x>n-1 and not flg:return False
        now=[x,s[x]]
  return True
l,r=0,n
# 左から落ちないゴーレムの最小座標
while r-l>1:
  x=(l+r)//2
  if bichk(x,True):
    l,r=l,x
  else:
    l,r=x,r
l0=l if bichk(l,True) else r

l,r=0,n
# 右から落ちないゴーレムの最大座標
while r-l>1:
  x=(l+r)//2
  if bichk(x,False):
    l,r=x,r
  else:
    l,r=l,x
r0=r if r<n and bichk(r,False) else l

print(max(0,r0-l0+1))
Problem p03090 (python)

Fixed submission:
n=int(input())
ans=[]
if n%2==0:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                ans.append([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                ans.append([i,j])
print(len(ans))
for i,j in ans:
    print(i,j)

Buggy submission (verdict: Runtime Error):
n=int(input())
ans=[]
if n%2==0:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n+1:
                ans.appned([i,j])
else:
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i+j!=n:
                ans.appned([i,j])
print(len(ans))
for i,j in ans:
    print(i,j)
Problem p03138 (python)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={j:0 for j in range(41)}
for ai in a:
  for j in range(41):
    if (ai>>j) & 1:
      d[j]+=1
ans=0
l=len(bin(k))-3
import sys
sys.setrecursionlimit(10**7)

def dp(m,t): # 一番左の桁（l桁目）から考える。一番右の桁は0桁目。t:kより真に小さいかどうか
  if m<0:return 0
  ret=0
  if t==1: # 以降は好きに選んでいいので、最適な数字を選ぶ。一意。
    for i in range(m+1):
      tmp=max(0,n-2*d[i])
      ret+=pow(2,i)*tmp
  else:
    if (k>>m)&1: #kのm桁目が1なら1か0を選べる
      # 1にするとき
      tmp1=dp(m-1,0)+(n-2*d[m])*pow(2,m)
      # 0にするとき
      tmp0=dp(m-1,1)                    
      ret+=max(tmp1,tmp0)
    else:
      ret+=dp(m-1,0)
  return ret

print(sum(a)+dp(l,0))

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={j:0 for j in range(32)}
for ai in a:
  for j in range(32):
    if (ai>>j) & 1:
      d[j]+=1
ans=0
l=len(bin(k))-3
import sys
sys.setrecursionlimit(10**7)

def dp(m,t): # 一番左の桁（l桁目）から考える。一番右の桁は0桁目。t:kより真に小さいかどうか
  if m<0:return 0
  ret=0
  if t==1: # 以降は好きに選んでいいので、最適な数字を選ぶ。一意。
    for i in range(m+1):
      tmp=max(0,n-2*d[i])
      ret+=pow(2,i)*tmp
  else:
    if (k>>m)&1: #kのm桁目が1なら1か0を選べる
      tmp1=dp(m-1,0)+(n-2*d[m])*pow(2,m)
      tmp0=dp(m-1,1)
      ret+=max(tmp1,tmp0)
    else:
      ret+=dp(m-1,0)
  return ret

print(sum(a)+dp(l,0))
Problem p03145 (python)

Fixed submission:
a,b,c=map(int,input().split())
print((a*b)//2)

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

print(8)

Buggy submission (verdict: Runtime Error):
"""
5 3
1 9
1 7
2 6
2 5
3 1
->26
7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5
->25
6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000
->4900000016
"""

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

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

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

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

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

Buggy submission (verdict: Runtime Error):
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=td[:k]
cat=list(set([tdi[0] for tdi in select]))
noselect=list(filter(lambda x: x[0] not in cat,td[k:]))
noselect.sort(key=lambda x:x[0])
noselect02=[]
noselect02.append(noselect[0])
for no in noselect[1:]:
    if no[0] != noselect[-1][0]:
        noselect.append(no)
        continue
    if no[1] > noselect[-1][1]:
        noselect[1]=no[1]

rs = sum([tdi[1] for tdi in select])+len(set([tdi[0] for tdi in select]))**2
for i in range(1,min(k,len(noselect)+1)):
    t = select[:-i]
    t[k-i:k-i] = noselect[:i]
    r = sum([tdi[1] for tdi in t])
    r += len(set([tdi[0] for tdi in t]))**2
    if rs < r:
        rs = r
print(rs)

Buggy submission (verdict: Runtime Error):
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=td[:k]
cat=list(set([tdi[0] for tdi in select]))
noselect=[]
tdk=td[k:]
tdk.sort(key=lambda x:x[0])
noselect.append(tdk[0])
for no in tdk[1:]:
    if no[0] != noselect[-1][0]:
        noselect.append(no)
        continue
    if no[1] > noselect[-1][1]:
        noselect[1]=no[1]

rs = sum([tdi[1] for tdi in select])+len(set([tdi[0] for tdi in select]))**2
for i in range(1,min(k,len(noselect)+1)):
    t = select[:-i]
    t[k-i:k-i] = noselect[:i]
    r = sum([tdi[1] for tdi in t])
    r += len(set([tdi[0] for tdi in t]))**2
    if rs < r:
        rs = r
print(rs)
Problem p03162 (python)

Fixed submission:
import numpy as np
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros((n+1,3),np.int64)
# dp[i][0]:i日目でaをとった時の最大。dp[0]=[0,0,0]。求めるのはmax(dp[n])
dp[1]=np.array(abc[0])
for i in range(2,n+1):
      dp[i][0]=abc[i-1][0]+max(dp[i-1][1],dp[i-1][2])
      dp[i][1]=abc[i-1][1]+max(dp[i-1][0],dp[i-1][2])
      dp[i][2]=abc[i-1][2]+max(dp[i-1][0],dp[i-1][1])

print(int(np.max(dp[-1])))

Buggy submission (verdict: Runtime Error):
import numpy as np
#n,k=map(int,input().split())
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros(n+1)
# dp[i]:i日目までの最大。dp[0]=0。求めるのはdp[n]
dp[1]=max(abc[0])
op1=[i for i in range(3) if abc[0][i]!=dp[1]]
if len(op1)<2:
      op1=[0,1,2]
op2=[0,1,2]
for i in range(2,n+1):
      m=max([abc[i-1][j] for j in op1])
      m1=dp[i-1]+m
      op=[j for j in range(3) if abc[i-1][j]!=m]
      if len(op)<2:
            op=[0,1,2]
      opt=[j for j in range(3) if abc[i-1][j]!=max(abc[i-1])]
      if len(op)<2:
            opt=[0,1,2]
      m2=dp[i-2]+max(abc[i-1])+max([abc[i-2][j] for j in set(op2).intersection(set(opt))])
      dp[i]=max(m1,m2)
      op2=op1
      op1=op

print(int(dp[-1]))