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

Fixed submission:
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  # dp0[i][j]:i列目の時点で残りちょうどj個取れる時の最大値
  rcv.sort(key=lambda x:C*R*x[0]+x[1])
  i=0
  nowc=0
  for j in range(R):
    # j+1行目に対する操作
    # 初期化
    for c in range(C):
      dp0[c][3]=max(dp0[c])
      dp0[c][2]=-inf
      dp0[c][1]=-inf
      dp0[c][0]=-inf
    nowc=0
    while i<K and rcv[i][0]==j+1:
      nextc=rcv[i][1]-1
      for k in range(nowc+1,nextc+1):
        dp0[k][0]=max(dp0[k][0],dp0[nowc][0])
        dp0[k][1]=max(dp0[k][1],dp0[nowc][1])
        dp0[k][2]=max(dp0[k][2],dp0[nowc][2])
      v=rcv[i][2]
      dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
      dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
      dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
      i+=1
      nowc=nextc
    for k in range(nowc+1,C):
      dp0[k][0]=max(dp0[k][0],dp0[nowc][0])
      dp0[k][1]=max(dp0[k][1],dp0[nowc][1])
      dp0[k][2]=max(dp0[k][2],dp0[nowc][2])
    #print(dp0)
  print(max(dp0[-1]))
if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  dp1=[[-inf]*4 for _ in range(C)]
  dp0[0][3]=0
  rcv.sort(key=lambda x:R*x[0]+x[1])
  i=0
  nowc=0
  while rcv[i][0]==1:
    nextc=rcv[i][1]-1
    for j in range(nowc+1,nextc+1):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
    v=rcv[i][2]
    dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
    dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
    dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
    i+=1
    nowc=nextc
    for j in range(nowc+1,C):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
  for j in range(1,R):
    for c in range(C):
      dp0[c][3]=max(dp0[c])
      dp0[c][2]=-inf
      dp0[c][1]=-inf
      dp0[c][0]=-inf
    nowc=0
    while i<K and rcv[i][0]==j+1:
      nextc=rcv[i][1]-1
      for k in range(nowc+1,nextc+1):
        dp0[k][0]=dp0[nowc][0]
        dp0[k][1]=dp0[nowc][1]
        dp0[k][2]=dp0[nowc][2]
      v=rcv[i][2]
      dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
      dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
      dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
      i+=1
      nowc=nextc
    for j in range(nowc+1,C):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
    #print(dp0)

  print(max(dp0[-1]))


if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  #import datetime
  #print(datetime.datetime.now())
  main(R,C,K,rcv)
  #print(datetime.datetime.now())
Problem p02647 (python)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,int(n**0.5)+10)):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(n**0.5+1):
  add_a=[0]*(n+1)
  for i in range(n):
    a[i]
    add_a[max(0,i-a[i])]+=1
    add_a[min(n,i+a[i]+1)]-=1
  tmp=0
  for i in range(n):
    tmp+=add_a[i]
    a[i]=tmp
print(' '.join(map(str,a)))
Problem p02670 (python)

Fixed submission:
from numba import njit
import numpy as np
@njit
def dfs(v,c,h,stay):
    # hを更新
    x,y=divmod(v,n)
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx,ny=x+dx,y+dy
        if 0<=nx<n and 0<=ny<n:
            nv=nx*n+ny
            if h[nv]>c:
                h[nv]=c
                dfs(nv,c+stay[nv],h,stay)

@njit
def main(n,p):
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0

    for v in p:
        c=h[v]
        ans+=c
        stay[v]=0
        dfs(v,c,h,stay)
    print(ans)

    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    n=int(input())
    p=np.array(list(map(int,input().split())),np.int32)
    p-=1
    main(n,p)

Buggy submission (verdict: Runtime Error):
def dfs(c,v,sheet,space,n):
  x,y=divmod(v,n)
  for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
    if 0<=x+dx<n and 0<=y+dy<n:
      nv=(x+dx)+(y+dy)*n
      if sheet[nv]>c:
        sheet[nv]=c
        dfs(c+space[nv],nv,sheet,space,n)

def main(n,p):
  sheet=[min(i%n,i//n,n-i%n-1,n-i//n-1) for i in range(n**2)]
  space=[1]*(n**2)
  #for i in range(n):
  #  print(sheet[i*n:(i+1)*n])
  ans=0
  for x in p:
    x-=1
    ans+=sheet[x]
    space[x]=0
    dfs(sheet[x],x,sheet,space,n)
  print(ans)

n=int(input())
p=list(map(int,input().split()))
main(n,p)

Buggy submission (verdict: Runtime Error):
from numba import njit
import numpy as np
@njit
def main():
    n=int(input())
    p=list(map(int,input().split()))
    h=[min(i//n,n-i//n-1,i%n,n-i%n-1) for i in range(n**2)]
    h=np.array(h)
    stay=np.full(n**2,1)
    ans=0
    def func(x,c):
        # hを更新
        todo=[[x,c]]
        seen=set(())
        while todo:
            v,c=todo.pop()
            nvs=[v+n,v-n]
            if v%n<n-1:nvs.append(v+1)
            if v%n>0:nvs.append(v-1)
            for nv in nvs:
                if nv<0 or n**2<=nv:continue
                if nv in seen:continue
                if h[nv]>c:
                    h[nv]=c
                    todo.append([nv,c+stay[nv]])
                seen.add(nv)
    for x in p:
        c=h[x-1]
        ans+=c
        stay[x-1]=0
        func(x-1,c)
    print(ans)
    #for i in range(n):
    #    print(h[i*n:(i+1)*n])
if __name__=='__main__':
    main()
Problem p02709 (python)

Fixed submission:
from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
#n=int(input())
#a_=list(map(int,input().split()))
import numpy as np
n=2000
a_=range(1,n+1)
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
dp[1,1]=a[0][1]*(n-a[0][0])
dp[1,0]=a[0][1]*(a[0][0]-1)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
      dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
      #i人目を左に
      l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
      #i人目を右に
      r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
      dp[i,1:i]=np.maximum(l,r)
print(max(dp[n]))
Problem p02716 (python)

Fixed submission:
from collections import defaultdict

n=int(input())
a=list(map(int,input().split()))
#n=2*pow(10,5)
#a=range(1,pow(10,5)+1)
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=defaultdict(lambda:-pow(10,18))
dp[(1,1)]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            if j==1:
                  dp[(i,j)]=max(dp[(i-1,1)],a[i-1])
            elif j==0:
                  dp[(i,j)]=0
            else:
                  dp[(i,j)]=max(dp[(i-2,j-1)]+a[i-1],dp[(i-1,j)])
print(dp[(n,n//2)])

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((3,n+1),-pow(10,15))
dp[1,1]=a[0]
for i in range(2,n+1):
    #l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
        now,pre,prepre=2,1,0
    elif i%3==0:
        now,pre,prepre=0,2,1
    elif i%3==1:
        now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=n//2-(n-i+1)//2,i//2+1
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((n+1,n+1),-pow(10,15))
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    dp[i,1:]=np.maximum(dp[i-1,1:],dp[i-2,:-1]+a[i-1])
print(dp[n,n//2])

Buggy submission (verdict: Runtime Error):
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.full((n+1,n+1),-1e+9)
dp[1,1]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(int(dp[n,n//2]))

Buggy submission (verdict: Runtime Error):
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.zeros((n+1,(n+1)//2+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(max(0,i//2-1),(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(dp[n,n//2])

Buggy submission (verdict: Runtime Error):
import numpy as np
n=int(input())
a=list(map(int,input().split()))
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=np.zeros((n+1,n+1),np.int64)
dp[1,1]=a[0]
dp[2,1]=max(a[:2])
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(max(0,i//2-1),(i+1)//2+1):
            dp[i,j]=max(dp[i-2,j-1]+a[i-1],dp[i-1,j])
print(dp[n,n//2])
Problem p02727 (python)

Fixed submission:

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
p=p[:x]
q=q[:y]
p[x:x]=q
p[x+y:x+y]=r
p.sort(reverse=True)
p=p[:x+y]
print(sum(p))

Buggy submission (verdict: Runtime Error):
#n,x,y=map(int,input())
# Queue
from collections import deque

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort()
q.sort()
p=deque(p[a-x:])
q=deque(q[b-y:])
r.sort()
for ri in r:
    if ri > p[0] and q[0] >= p[0]:
        p.popleft()
        p.append(ri)
        p.sort()
        continue
    if ri > q[0] and p[0] >= q[0]:
        q.popleft()
        q.sort()
        q.append(ri)
print(sum(p)+sum(q))

"""
1 2 2 2 1
2 4
5 1
3
->12
2 2 2 2 2
8 6
9 1
2 1
->25
"""
Problem p02749 (python)

Fixed submission:
n=int(input())
ki=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    ki[a].append(b)
    ki[b].append(a)

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==1:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')

Buggy submission (verdict: Runtime Error):
n=int(input())
ki=[[] for _ in range(n)]

for _ in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    ki[a].append(b)
    ki[b].append(a)

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<n//3:
    cnt1=1
    cnt=2
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==0:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')
Problem p02756 (python)

Fixed submission:
s=input()
n=int(input())
q=[]
for _ in range(n):
  q.append(input().split())
sw=True #奇数回文字列の前後を入れ替えているときFalseになる
sl=''
sr=''
for i in range(n):
  if q[i][0]=='1':
    sw = not sw
  else:
    if q[i][1]=='1' and sw==True:
      sl += q[i][2]
    elif q[i][1]=='2' and sw==False:
      sl += q[i][2]
    else:
      sr +=q[i][2]

ans=''
if sw:
  for i in range(len(sl)):
    ans+=sl[len(sl)-1-i]
  print(ans+s+sr)
else:
  for i in range(len(sr)):
    ans+=sr[len(sr)-1-i]
  for i in range(len(s)):
    ans+=s[len(s)-1-i]
  print(ans+sl)

Buggy submission (verdict: Runtime Error):
s=input()
n=int(input())
q=[]
for _ in range(n):
  q.append(input().split())
sw=True #奇数回文字列の前後を入れ替えているときFalseになる
sl=''
sr=''
for i in range(n):
  if q[i][0]=='1':
    sw = not sw
  else:
    if q[i][1]=='1' and sw==True:
      for j in range(len(q[i][2])):
        sl += q[i][2][len(q[i][2])-1-j]
    elif q[i][1]=='2' and sw==False:
        sl += q[i][2][len(q[i][2])-1-j]
    else:
      sr +=q[i][2]

ans=''
if sw:
  for i in range(len(sl)):
    ans+=sl[len(sl)-1-i]
  print(ans+s+sr)
else:
  for i in range(len(sr)):
    ans+=sr[len(sr)-1-i]
  print(ans+s+sl)
Problem p02782 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  def cmb(n, r, mod):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return g1[n] * g2[r] * g2[n-r] % mod
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()

Buggy submission (verdict: Runtime Error):
r1,c1,r2,c2=map(int,input().split())
mod=pow(10,9)+7

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
n=max(r1,c1,r2,c2)
for i in range(2,2*10**6+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
ans=0
for k in range(r1,r2+1):
  tmp=cmb(k+1+c2,c2,mod)-cmb(k+1+c1-1,c1-1,mod)
  ans+=tmp
  ans%=mod
print(ans)
Problem p02787 (python)

Fixed submission:
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(10**4+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[h])

Buggy submission (verdict: Runtime Error):
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(h+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[-1])
Problem p02788 (python)

Fixed submission:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
from collections import deque
minusd=deque()
nowd=0
ans=0
for x,h in xh:
  while minusd and minusd[0][1]<=x:
    d_,_=minusd.popleft()
    nowd-=d_
  tmp=max(0,(h-nowd+a-1)//a)
  ans+=tmp
  nowd+=tmp*a
  minusd.append([tmp*a,x+2*d+1])
  #print(ans,nowd)
print(ans)

Buggy submission (verdict: Runtime Error):
n_,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n_)]
"""
n_=2*1000
d=0 #pow(10,9)
a=1
xh=[[pow(10,9)//i,pow(10,9)] for i in range(1,1+n_)]
"""
xh.sort(key=lambda x:x[0])

#A1 ... AnのBIT(1-indexed)
n=xh[-1][0]
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    if idx==0:
      return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
  if idx==0:
    print('index 0!')
    return 
  while idx <= n:
      BIT[idx] += x
      idx += idx&(-idx)
  return

ans=0
for x,h in xh:
  fd=BIT_query(min(x+2*d,xh[-1][0]))-BIT_query(max(0,x-1))
  if h-fd<=0:
    pass
  else:
    c=(h-fd)//a
    BIT_update(min(x+2*d,xh[-1][0]),c*a)
    ans+=c
  pre_x=x
print(ans)

Buggy submission (verdict: Runtime Error):
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
"""
n=2*100000
d=0
a=1
xh=[[pow(10,9)//i,pow(10,9)] for i in range(1,1+n)]
"""
xh.sort(key=lambda x:x[0])
import numpy as np
fd=np.zeros(2*d+1,np.int64) # fd[i]:ターゲットのモンスターから座標+i離れたところにいるモンスターに与えたダメージ
ans=0
pre_x=xh[0][0]
for x,h in xh:
  fdt=np.zeros(2*d+1,np.int64)
  if 0<x-pre_x and x-pre_x<2*d+1:
    fdt[:-x+pre_x]=fd[x-pre_x:]
  fd=fdt
  if h-fd[0]<=0:
    pass
  else:
    c=(h-fd[0]+a-1)//a
    fd+=c*a
    ans+=c
  pre_x=x
print(ans)

Buggy submission (verdict: Runtime Error):
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
import numpy as np
fd=np.zeros(xh[-1][0]+1,np.int64) # fd[i]:座標iにいるモンスターに与えたダメージ
ans=0
for x,h in xh:
  if h-fd[x]<=0:
    continue
  else:
    c=(h-fd[x]+a-1)//a
    fd[x:min(xh[-1][0]+1,x+2*d+1)]+=c*a
    ans+=c
print(ans)

Buggy submission (verdict: Runtime Error):
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
import numpy as np
fd=np.zeros(xh[-1][0]+1,np.int64) # fd[i]:座標iにいるモンスターに与えたダメージ
ans=0
for x,h in xh:
  if h-fd[x]<=0:
    continue
  else:
    c=(h-fd[x]+a-1)//a
    fd[x:x+2*d+1]+=c*a
    ans+=c
print(ans)
Problem p02804 (python)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))


mod=pow(10,9)+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import Counter
cnt_a=Counter(a)
list_a=list(cnt_a.keys())
list_a.sort()
num_a=len(list_a)
sa_=0
sa=[0]
for ai in list_a:
    sa_+=cnt_a[ai]
    sa.append(sa_)
ansmin=0
ansmax=0
for i in range(num_a):# list_a[i]がminになる場合の数
    k_=sa[num_a]-sa[i]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmin+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmin%=mod
for i in range(num_a):# list_a[i]がmaxになる場合の数
    k_=sa[i+1]
    if k_>=k:
        mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
        ansmax+=list_a[i]*(cmb(k_,k,mod)-mi)
        ansmax%=mod
print((ansmax-ansmin)%mod)

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=pow(10,9)+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import Counter
cnt_a=Counter(a)
list_a=list(cnt_a.keys())
list_a.sort()
num_a=len(list_a)
sa_=0
sa=[0]
for ai in list_a:
    sa_+=cnt_a[ai]
    sa.append(sa_)

ans=0
for i in range(num_a): 
    for j in range(i,num_a):# list_a[i]をmin,list_a[j]をmaxとしてk個選べるか
        k_=sa[j+1]-sa[i]
        if k_>=k:
            mj=0 if k_-cnt_a[list_a[j]]<k else cmb(k_-cnt_a[list_a[j]],k,mod)
            mi=0 if k_-cnt_a[list_a[i]]<k else cmb(k_-cnt_a[list_a[i]],k,mod)
            ans+=(list_a[j]-list_a[i])*(cmb(k_,k,mod)-mj-mi)
            ans%=mod
            #f(x)の値×list_a[i]をmin,list_a[j]をmaxとしてk個選ぶ選び方
print(ans)