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

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

n=int(input())
a=list(map(float,input().split()))
dp=[[0.0 for _ in range(n+1)] for _ in range(n+1)]
dp[1][1]=a[0]
dp[1][0]=1-a[0]
 
for i in range(2, n+1):
    for j in range(i+1):
        dp[i][j]=a[i - 1] * dp[i - 1][j - 1]+(1 - a[i - 1])*dp[i - 1][j]
 
print(sum(dp[n][n // 2 + 1:]))

Buggy submission (verdict: Runtime Error):
n=int(input())
a=list(map(float,input().split()))
dp={}

def foo(i,h,t,p):
	if i==n-1:
		if h>t:
			return p
		else:
			return 0
	return foo(i+1,h+1,t,p*a[i+1])+foo(i+1,h,t+1,p*(1-a[i+1]))

print(foo(-1,0,0,1))
Problem p03160 (python)

Fixed submission:
def expand_result(result, h, t):
    if t <= 0:
        result.append(0)
    elif t == 1:
        result.append(abs(h[1] - h[0]))
    else:
        result.append(min(result[t - 1] + abs(h[t] - h[t - 1]), result[t - 2] + abs(h[t] - h[t - 2])))
    return result

n = int(input())
h = input().split(" ")
h = list(map(int, h))
result = []
for i in range(n):
    result = expand_result(result, h, i)
print(result[n - 1])

Buggy submission (verdict: Runtime Error):
def cost(list, t):
    if t <= 0:
        return 0
    elif t == 1:
        return abs(list[1] - list[0])
    else:
        return min(cost(list, t - 1) + abs(list[t] - list[t - 1]), cost(list, t - 2) + abs(list[t] - list[t - 2]))

n = int(input())
h = input().split(" ")
h = list(map(int, h))
print(cost(h, n - 1))
Problem p03162 (python)

Fixed submission:
n = int(input())
a, b, c = [], [], []
for i in range(n):
    h = input().split(" ")
    a.append(int(h[0]))
    b.append(int(h[1]))
    c.append(int(h[2]))
sum_a, sum_b, sum_c = [a[0]], [b[0]], [c[0]]
for i in range(1, n):
    sum_a.append(a[i] + max(sum_b[i - 1], sum_c[i - 1]))
    sum_b.append(b[i] + max(sum_c[i - 1], sum_a[i - 1]))
    sum_c.append(c[i] + max(sum_a[i - 1], sum_b[i - 1]))
print(max(sum_a[n - 1], sum_b[n - 1], sum_c[n - 1]))

Buggy submission (verdict: Runtime Error):
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
Problem p03161 (python)

Fixed submission:
import sys

def solve(n,k,ar):

    dp = [sys.maxsize]*n
    dp[0] = 0

    for i in range(n):
        for k in range(1,k+1):
            if i+k <= n-1:
                dp[i+k] = min(dp[i+k], dp[i] + abs(ar[i]-ar[i+k]))

    print(dp[n-1])



if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)

Buggy submission (verdict: Runtime Error):
import sys

def solve(n,k,ar):

    dp = [sys.maxsize]*n
    dp[0] = 0

    for i in range(n):
        for j in range(1,k+1):
            if i+j < n:
                dp[i+k] = min(dp[i+k], dp[i] + abs(ar[i]-ar[i+k]))

    print(dp[n-1])



if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)

Buggy submission (verdict: Runtime Error):
def solve(n,k,ar):

    dp = [0]*n
    dp[0] = 0

    for i in range(1, n):
        for j in range(max(0, i - k), i):
            dp[i] = min(dp[j] + abs(ar[i] - ar[j]))

    print(dp[n-1])



if __name__ == '__main__':
    n,k = map(int,input().split())
    ar = list(map(int,input().split()))

    solve(n,k,ar)
Problem p03161 (python)

Fixed submission:
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if k>n:
    k=n-1
dp=[int(0) for _ in range(n)]
dp[1]=abs(a[0]-a[1])
 
for i in range(2,n):
  ind = max(0,i-k)
  dp[i]=min([dp[v]+abs(a[i]-a[v]) for v in range(ind,i)])
  #dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))
#print(dp[n-1])
print(dp[-1])

Buggy submission (verdict: Runtime Error):
import numpy as np
n,k=list(map(int,input().split()))
a=np.array(map(int,input().split()))
if k>n:
   k=n-1
dp=np.array([int(0) for _ in range(n)])
dp[1]=abs(a[0]-a[1])
 
for i in range(2,n):
  ind = max(0,i-k)
  dp[i]=np.min(np.add(dp[ind:i],np.abs(a[i]-a[ind:i])))
print(dp[-1])

Buggy submission (verdict: Runtime Error):
import numpy as np
n,k=list(map(int,input().split()))
a=np.array(map(int,input().split()))
if k>n:
   k=n-1
dp=np.array([int(0) for _ in range(n)])
dp[1]=abs(a[0]-a[1])
 
for i in range(2,n):
  ind = max(0,i-k)
  dp[i]=np.min(np.add(dp[ind:i],np.abs(a[i]-a[ind:i])))
print(dp[-1])

Buggy submission (verdict: Runtime Error):
    n,k=list(map(int,input().split()))
    a=list(map(int,input().split()))
    if k>n:
        k=n-1
    dp=np.array([int(0) for _ in range(n)])
    dp[1]=abs(a[0]-a[1])
     
    for i in range(2,n):
      ind = max(0,i-k)
      dp[i]=np.minimum(np.sum(dp[ind:i],abs(a[i]-a[ind:i])))
      #dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))
    #print(dp[n-1])
    print(dp[-1])

Buggy submission (verdict: Runtime Error):
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if k>n:
    k=n-1
dp=np.array([int(0) for _ in range(n)])
dp[1]=abs(a[0]-a[1])
 
for i in range(2,n):
  ind = max(0,i-k)
  dp[i]=np.minimum(np.sum(dp[ind:i]+abs(a[i]-a[ind:i]))s)
  #dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))
#print(dp[n-1])
print(dp[-1])
Problem p03162 (python)

Fixed submission:
n=int(input())

dp=list(map(int,input().split()))
for day in range(1,n):
    m=[0]*3
    day_points=list(map(int, input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                 m[i]=max(m[i],day_points[i]+dp[j])
    dp=m
print(max(dp))

Buggy submission (verdict: Runtime Error):
n = int(input())
last_chosen = -1

max_points = 0
for i in range(n):
    days = list(map(int, input().split()))
    while True:
        act = max(days)
        idx = days.index(act)
        if idx != last_chosen:
            break
        days.pop(idx)
    max_points += days[idx]
    last_chosen = idx
print(max_points)

Buggy submission (verdict: Runtime Error):
n = int(input())
last_chosen = -1

max_points = 0
for i in range(n):
    days = list(map(int, input().split()))
    while True:
        act = max(days)
        idx = days.index(act)
        if idx != last_chosen:
            break
        days.pop(idx)
    max_points += days[idx]
    last_chosen = idx
print(max_points)
Problem p03166 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
  dp[i]=temp  
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())

grid=[]
for i in range(n):
  x=list(input())
  grid.append(x)
  

dp=[[0 for i in range(m)] for j in range(n)]
dp[0][0]=1
for i in range(n):
  for j in range(m):
    if grid[i][j]!='#':
      if i>0:
        dp[i][j]+=dp[i-1][j]
      if j>0:
        dp[i][j]+=dp[i][j-1]
        
print(dp[n-1][m-1]%(10**9+7))

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  temp=0
  for nv in g[i]:
    if dp(nv)!=-1:
      temp=max(temp, dp[nv])
    else:  
    	temp=max(temp,dfs(nv)+1)
    dp[i]=temp
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  temp=0
  for nv in g[i]:
    if dp(nv)!=-1:
      temp=max(temp, dp[nv])
    else:  
    	temp=max(temp,dfs(nv)+1)
    
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)
Problem p03168 (python)

Fixed submission:
n=int(input())
p=list(map(float, input().split()))
       
dp=[[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=1

for i in range(1,n+1):
       for j in range(n+1):
       	if j==0:
       		dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
       	else:
       		dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]
res=0
for i in range(n//2+1,n+1):
       res+=dp[n][i]
print(res)

Buggy submission (verdict: Runtime Error):
n=int(input())
p=list(map(float, input().split())
       
dp=[[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=1

for i in range(1,n+1):
       for j in range(n+1):
       	if j==0:
       		dp[i][j]=(1.0-p[i-1])*dp[i-1][j]
       	else:
       		dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j]
res=0
for i in range(n//2+1,n+1):
       res+=dp[n][i]
print(res)
Problem p03163 (python)

Fixed submission:
# from sys import stdin, stdout
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,capacity+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Buggy submission (verdict: Runtime Error):
# from sys import stdin, stdout
n,capacity=map(int,input().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,input().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,weights+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout
n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
dp=[[0]*(capacity+1) for i in range(n+1)]
for i in range(n+1):
    for j in range(weights+1):
        if(weights[i-1]<=j):
            dp[i][j]=max(values[i-1]+dp[i-1][j-weights[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][capacity])

Buggy submission (verdict: Runtime Error):
from sys import stdin, stdout
def knapsack(weights,values,capacity,n,memo):
    if(memo[n][capacity]!=-1):
        return memo[n][capacity]
    if(n==0 or capacity==0):
        return 0
    val=0
    left=values[n-1]+knapsack(weights,values,capacity-weights[n-1],n-1,memo)
    right=knapsack(weights,values,capacity,n-1,memo)
    if(weights[n-1]<=capacity):
        temp=max(left,right)
        memo[n][capacity]=temp
        return temp
    memo[n][capacity]=right
    return right

n,capacity=map(int,stdin.readline().split())
weights=[0]*n
values=[0]*n
for i in range(n):
    weights[i],values[i]=map(int,stdin.readline().split())
memo=[[-1]*(capacity+1) for i in range(n+1)]
stdout.write(str(knapsack(weights,values,capacity,n,memo)))
Problem p03165 (python)

Fixed submission:
import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for i in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))

Buggy submission (verdict: Runtime Error):
import sys

# 最長部分列の長さを求める
# 0行と0列は0
def lcs_count(A,B):
    # initial value setting
    dp = [[0]*(l2+1) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
#    for line in dp:
#        print(line)
    return dp

def lcs_string(dp): 
    string = []
    i = l1-1
    j = l2-1
    while i > 0 and j > 0:
        if t[i - 1] == t[j - 1]:
            string.insert(0,chr(s[i-1]+97))
            i, j = i - 1, j - 1
        elif dp[i][j - 1] > dp[i - 1][j]:
            j -= 1
        else:
            i -= 1
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
#print(DP[l1][l2])
lcs_string(DP)

Buggy submission (verdict: Runtime Error):
import sys

def main():
  s = sys.stdin.readline().rstrip()
  t = sys.stdin.readline().rstrip()
  l1 = len(s)
  l2 = len(t)

  DP = lcs_count(s,t)
  lcs_string(DP)

  def lcs_count(A,B):
      # initial value setting
      dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
      # create table
      for i in range(1,l1+1):
          for j in range(1,l2+1):
              if A[i-1] == B[j-1]:
                  dp[i][j] = dp[i-1][j-1] + 1
              else:
                  dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      return dp

  def lcs_string(dp):
      string = []
      S = [m for m in range(l1,0,-1)]
      T = [n for n in range(l2,0,-1)]
      for i,j in zip(S,T):
          if dp[i][j] > dp[i-1][j-1]:
              string.insert(0,s[i-1])
      print("".join(string))

main()
Problem p03181 (python)

Fixed submission:


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])

Buggy submission (verdict: Runtime Error):


def dfs1(u, pu):
    dp[u] = 1
    for v in tree[u]:
        if v != pu:
            dfs1(v, u)
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

def dfs2(u, pu, pval):
    resp[u] = (dp[u] * pval) % MOD
    
    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval
    for i in range(len(chlds)):
        v = chlds[i]
        vval = (1 + pref * cumulr[i]) % MOD

        dfs2(v, u, vval)

        pref *= (dp[v] + 1)
        pref %= MOD


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)

dp = [0] * n
resp = [0] * n
dfs1(0, -1)
dfs2(0, -1, 1)
for i in range(n):
    print(resp[i])
Problem p03703 (python)

Fixed submission:
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+5)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*(n+1)
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=[0]+[int(input())-k for i in range(n)]
for i in range(1,n+1):
	a[i]+=a[i-1]
b=sorted(a)+[-2e9-1]
c,d=0,dict()
for i in range(n+1):
	if b[i]!=b[i-1]:
		c+=1
		d[b[i]]=c
bit=[0]*n
def sum(i):
	res=0
	while i>0:
		res+=bit[i]
		i-=i&-i
	return res
def add(i):
	while i<=c:
		bit[i]+=1
		i+=i&-i
ans=0
for i in range(n+1):
	ans+=sum(d[a[i]])
	add(d[a[i]])
print(ans)
Problem p03787 (python)

Fixed submission:
import queue
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x):
	stk,flag=queue.LifoQueue(),True
	stk.put((x,1))
	while not stk.empty():
		u,col=stk.get()
		if vis[u]:
			flag&=(vis[u]==col)
			continue
		vis[u]=col
		for i in g[u]:
			stk.put((i,3-col))
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Buggy submission (verdict: Runtime Error):
import sys

class TailRecurseException:
	def __init__(self, args, kwargs):
		self.args = args
		self.kwargs = kwargs

def tail_call_optimized(g):
	def func(*args, **kwargs):
		f = sys._getframe()
		if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
			raise TailRecurseException(args, kwargs)
		else:
			while 1:
				try:
					return g(*args, **kwargs)
				except TailRecurseException, e:
					args = e.args
					kwargs = e.kwargs
	func.__doc__ = g.__doc__
	return func

n,m=map(int,raw_input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,raw_input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+5),0,0,0
g=[[] for i in range(n+5)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Buggy submission (verdict: Runtime Error):
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)
Problem p03788 (python)

Fixed submission:
n,k=map(int,input().split())
s=list(input())*3
p=['A' if s[i]=='B' else 'B' for i in range(n)]*3
head,tail=0,n
for i in range(2*n):
	if s[head]=='A':
		s[head],p[head]='B','A'
	else:
		s,p=p,s
		head+=1
		s[tail],p[tail]='A','B'		
		tail+=1
	if i==k-1:
		print(''.join(s[head:tail]))
		break
else:
	if n%2==1 and k%2==1:
		if s[head]=='A':
			s[head],p[head]='B','A'
		else:
			s,p=p,s
			head+=1
			s[tail],p[tail]='A','B'		
			tail+=1
	print(''.join(s[head:tail]))

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=list(input())*2
p=['A' if s[i]=='B' else 'B' for i in range(n)]*2
head,tail=0,n
for i in range(2*n):
	if s[0]=='A':
		s[0],p[0]='B','A'
	else:
		s,p=p,s
		head+=1
		s[tail],p[tail]='A','B'
		tail+=1
	if i==k-1:
		print(''.join(s[head:tail]))
		break
else:
	if n%2==1 and k%2==1:
		if s[0]=='A':
			s[0],p[0]='B','A'
		else:
			s,p=p,s
			head+=1
			s[tail],t[tail]='A','B'
			tail+=1
	print(''.join(s[head:tail]))
Problem p03183 (python)

Fixed submission:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])
U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)
print(dp.max())

Buggy submission (verdict: Runtime Error):
n = int(input())
unsorted_blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    unsorted_blocks.append({"w": w, "s": s, "v": v})

blocks = sorted(unsorted_blocks, key=lambda block: unsorted_blocks["s"]) 

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i and blocks[x]["w"] <= new_max_s]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))
Problem p03184 (python)

Fixed submission:
import sys
h, w, n = [int(i) for i in sys.stdin.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i % m)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.stdin.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])

Buggy submission (verdict: Runtime Error):
import sys
h, w, n = [int(i) for i in sys.readline().split()]
m = 1000000007
fact = [1, 1]
for i in range(2, 200002):
    fact.append(fact[-1] * i)
inv = [pow(i, m - 2, m) for i in fact]
f = lambda i: fact[i[0] + i[1]] * inv[i[0]] * inv[i[1]] % m
dp = [0] * (n + 1)
p = [[int(i) - 1 for i in sys.readline().split()] for j in range(n)]
p = sorted(p + [[h - 1, w - 1]])
for i in range(n + 1):
    h1, w1 = p[i]
    tot = f([h1, w1])
    for j in range(i):
        if p[j][1] > w1:
            continue
        tot = (tot - dp[j] * f([h1 - p[j][0], w1 - p[j][1]]) % m) % m
    dp[i] = tot
print(dp[-1])