Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys

n,k = map(int, input().split())
td = []
td_mx = {}
for _ in range(n):
  t,d = map(int, input().split())
  td.append(d)
  if (t not in td_mx) or (td_mx[t] < d):
    td_mx[t] = d
td = sorted(td)
td_mx = sorted(td_mx.values())

mx_sum = 0
t_mx = len(td_mx)
ans = 0
for t in range(1, min(t_mx,k)+1):
  mx_sum += td_mx[-1]
  td.remove(td_mx[-1])
  td_mx.pop(-1)
  if t < k:
    ans = max(ans, mx_sum + sum(td[-k+t:]) + t**2)
  else:
    ans = max(ans, mx_sum + t**2)

print(ans)


Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n,k = map(int, input().split())
td_mx = {}
td = []
for _ in range(n):
  t,d = map(int, input().split())
  if t not in td_mx:
    td_mx[t] = d
  elif td_mx[t] < d:
    td.append(td_mx[t])
    td_mx[t] = d
  else:
    td.append(d)
td = sorted(td, key=lambda x:-x)
td_mx = sorted(td_mx.values(), key=lambda x:-x)

# td,td_mx の累積和を求める
csum = [0]
csum_mx = [0]
for i in range(len(td)):
  csum.append(csum[-1] + td[i])
for i in range(len(td_mx)):
  csum_mx.append(csum_mx[-1] + td_mx[i])


# 1~k種類で探索 最大値を取り出す
ans = 0
for i in range(1,k+1):
  if i <= len(csum_mx)-1 and k-i <= len(csum)-1:
    ans = max(ans, csum_mx[i] + csum[k-i] + i*i)
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N = int(input())
a = [0]*100001
b = [0]*100001
c = [0]*100001

for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())


### solve
hpns = [[0 for j in range(101)] for i in range(3)]

for i in range(1, N+1):
	hpns[0][i] = max(hpns[1][i-1], hpns[2][i-1]) + a[i-1]
	hpns[1][i] = max(hpns[2][i-1], hpns[0][i-1]) + b[i-1]
	hpns[2][i] = max(hpns[0][i-1], hpns[1][i-1]) + c[i-1]
	
print(max(hpns[0][N], hpns[1][N], hpns[2][N]))

Fixed submission:
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N = int(input())
a = [0]*100001
b = [0]*100001
c = [0]*100001

for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())


### solve
hpns = [[0 for j in range(100001)] for i in range(3)]

for i in range(1, N+1):
	hpns[0][i] = max(hpns[1][i-1], hpns[2][i-1]) + a[i-1]
	hpns[1][i] = max(hpns[2][i-1], hpns[0][i-1]) + b[i-1]
	hpns[2][i] = max(hpns[0][i-1], hpns[1][i-1]) + c[i-1]
	
print(max(hpns[0][N], hpns[1][N], hpns[2][N]))
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


N,W = map(int, sys.stdin.readline().rstrip().split())
wv = []
for _ in range(N):
  wv.append(list(map(int, sys.stdin.readline().rstrip().split())))

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(1,N+1):
  for j in range(1, W+1):
    if j < wv[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])

print(max(dp[N]))

Fixed submission:
# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
  w,v = map(int, sys.stdin.readline().rstrip().split())
  np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
# /user/bin/python
# -*- coding: utf-8 -*-
import math
import sys

n,w = map(int, sys.stdin.readline().rstrip().split())
weight = [0] * n
value = [0] * n
for i in range(n):
  weight[i], value[i] = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
  for j in range(w+1):
    if j >= weight[i]:
      dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
    else:
      dp[i+1][j] = dp[i][j]

print(dp[n][w])

Fixed submission:
# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
  w,v = map(int, sys.stdin.readline().rstrip().split())
  np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

N,W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
  w[i],v[i] = map(int, input().split())

dp = [float('inf')] * (10**5+1)
dp[0] = 0

MAX_V = 0
for i in range(N):
  MAX_V += v[i]
  for j in range(MAX_V,-1,-1):
    if j >= v[i] and dp[j-v[i]]+w[i] <= W:
      dp[j] = min(dp[j], dp[j-v[i]]+w[i])

ans = 0
for i in range(len(dp)):
  if dp[i] < float('inf'):
    ans = max(ans, i)
print(ans)

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys

N,W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
  w[i],v[i] = map(int, input().split())

dp = [float('inf')] * (sum(v)+1)
dp[0] = 0

MAX_V = 0
ans = 0
for i in range(N):
  MAX_V += v[i]
  for j in range(MAX_V,-1,-1):
    if j >= v[i] and dp[j-v[i]]+w[i] <= W:
      ans = max(ans,j)
      dp[j] = min(dp[j], dp[j-v[i]]+w[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
input = sys.stdin.readline

a, b = map(int, input().rstrip().split())
print(a + b // 2)# -*- coding: utf-8 -*-

import math
import sys
from operator import itemgetter
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':

a, b = map(int, input().rstrip().split())
print(a + b // 2)

Fixed submission:
x, y = map(int, input().split())
print(x + y // 2)

Buggy python submission (verdict: Runtime Error):
input = sys.stdin.readline

a, b = map(int, input().rstrip().split())
print(a + b // 2)

Fixed submission:
x, y = map(int, input().split())
print(x + y // 2)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':


def divisors(p, q):
	ans = []
	if q == 1:
		ans = [1]
	else:
		for i in range(2, q // p + 1):
			if q % i == 0:
				ans.append(i)
	return(ans)

N, M = map(int, input().rstrip().split())
print(divisors(N, M)[-1])

Fixed submission:
# -*- coding: utf-8 -*-

import math
import sys
import heapq
from operator import itemgetter
import itertools
input = sys.stdin.readline

# a = int(input().rstrip())
# a, b = map(int, input().rstrip().split())
# D = list(map(int, input().rstrip().split()))
# H = [int(input().rstrip()) for _ in range(L)]
# DD = [[0 for j in range(100)] for i in range(200)]
# dict = {} ## dictionary

# a = sorted(a, key=lambda x: x[1]))
# if __name__ == '__main__':


def divisors(n, m):
	for i in range(m//n, 0, -1):
		if m % i == 0:
			return(i)


N, M = map(int, input().rstrip().split())
print(divisors(N, M))
Buggy python submission (verdict: Time Limit Exceeded):
# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

n = int(sys.stdin.readline().rstrip())
v_s = list(map(int, sys.stdin.readline().rstrip().split()))

eval_type = {}
odd_type = {}

# v を eo_type(dict) に追加する
def add_v(eo_type, v):
  if v not in eo_type:
    eo_type[v] = 1
  else:
    eo_type[v] += 1

# eo_type(dict) の max value 2つの index を返す
def get_max2(eo_type):
  mx1, mx2 = [0] * 2
  for i in eo_type:
    if (mx1 not in eo_type) or (eo_type[mx1] < eo_type[i]):
      mx2 = mx1
      mx1 = i
    elif (mx2 not in eo_type) or (eo_type[mx2] < eo_type[i]):
      mx2 = i
  return([mx1, mx2])


def solve(idx_e, idx_o):
  if idx_e == 0 or idx_o == 0:
    return(sys.maxsize)
  elif idx_e == idx_o:
    return(min(n-eval_type[idx_e], n-odd_type[idx_o]))
  else:
    return(n - eval_type[idx_e] - odd_type[idx_o])


if __name__ == "__main__":
  for i in range(len(v_s)):
    if i % 2 == 0:
      add_v(eval_type, v_s[i])
    else:
      add_v(odd_type, v_s[i])
  
    ve1,ve2 = get_max2(eval_type)
    vo1,vo2 = get_max2(odd_type)
  
  print(min(solve(ve1,vo1), solve(ve1,vo2), solve(ve2,vo1)))
  

Fixed submission:
# /user/bin/python
# -*- coding: utf-8 -*-
from collections import Counter
import sys

n = int(sys.stdin.readline().rstrip())
v_s = list(map(int, sys.stdin.readline().rstrip().split()))

v_even = Counter(v_s[0::2]).most_common()
v_even.append((0,0))
v_odd = Counter(v_s[1::2]).most_common()
v_odd.append((0,0))

if v_even[0][0] != v_odd[0][0]:
  print(n-v_even[0][1]-v_odd[0][1])
else:
  print(min(n-v_even[0][1]-v_odd[1][1], n-v_odd[0][1]-v_even[1][1]))
Buggy python submission (verdict: Time Limit Exceeded):
# /user/bin/python
# -*- coding: utf-8 -*-
import sys
import numpy as np


D,G = map(int, sys.stdin.readline().rstrip().split())
G //= 100
P = [0]
C = [0]
for _ in range(D):
  p,c = map(int, sys.stdin.readline().rstrip().split())
  P.append(p)
  C.append(c//100)


dp = [[sys.maxsize for j in range(G+1)] for i in range(D+1)]
for i in range(D+1):
  dp[i][0] = 0

for i in range(1,D+1):
  for j in range(1,G+1):
    for q in range(P[i]):
      dp[i][j] = min(dp[i][j], dp[i-1][max(0, j-i*q)] + q)
    q = P[i]
    dp[i][j] = min(dp[i][j], dp[i-1][max(0, j-i*q-C[i])] + q)

print(dp[D][G])

Fixed submission:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys


D,G = list(map(int, input().split()))
PC = [0]+[list(map(int, input().split())) for _ in range(D)]
 
def function(G, i):
	if i == 0:
		return 1e9
	n = min(G//(i*100), PC[i][0])
	s = n*i*100
	if n == PC[i][0]:
		s += PC[i][1]
	if s < G:
		n += function(G-s, i-1)
	return min(n, function(G,i-1))

print(function(G, D))
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
# -*- coding: utf-8 -*-
MOD = 1000000007


def main():
  S = str(input())
  dp = [[0 for _ in range(3)] for _ in range(len(S)+1)]
  A,AB,ABC = [0,1,2]
  wc_num = 0
  for i,s in enumerate(S):
    if s in "A?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]+3**wc_num) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "B?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]+dp[i][A]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "C?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]+dp[i][AB]) % MOD
    if s == "?":
      wc_num += 1
  print(dp[len(S)][ABC])



if __name__ == "__main__":
  main()

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
MOD = 1000000007


def main():
  S = str(input())
  dp = [[0 for _ in range(3)] for _ in range(len(S)+1)]
  A,AB,ABC = [0,1,2]
  wc_num = 1
  for i,s in enumerate(S):
    if s in "A?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]+wc_num) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "B?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]+dp[i][A]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]) % MOD
    if s in "C?":
      dp[i+1][A] = (dp[i+1][A]+dp[i][A]) % MOD
      dp[i+1][AB] = (dp[i+1][AB]+dp[i][AB]) % MOD
      dp[i+1][ABC] = (dp[i+1][ABC]+dp[i][ABC]+dp[i][AB]) % MOD
    if s == "?":
      wc_num = (wc_num*3) % MOD
  print(dp[len(S)][ABC])



if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


## input
N = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
sum = [0] * (N+1)
for i in range(1, N+1):
  sum[i] = sum[i-1] + An[i]

ans = sys.maxsize
for i in range(2, N-1):
  ## Split BC
  left, right = 1, i
  while(right-left > 1):
    mid = (left + right) // 2
    sum_l = sum[mid]
    sum_r = sum[i] - sum[mid]
    if sum_l > sum_r:
      left, right = left, mid
    else:
      left, right = mid, right

  P1,Q1 = sum[left], sum[i] - sum[left]
  P2,Q2 = sum[right], sum[i] - sum[right]
  if abs(P1-Q1) >= abs(P2-Q2):
    P,Q = P2, Q2
  else:
    P,Q = P1, Q1

  ## Split DE
  left, right = i+1, N
  while(right-left > 1):
    mid = (left + right) // 2
    sum_l = sum[mid] - sum[i]
    sum_r = sum[N] - sum[mid]
    if sum_l > sum_r:
      left, right = left, mid
    else:
      left, right = mid, right

  R1,S1 = sum[left]-sum[i], sum[N]-sum[left]
  R2,S2 = sum[left+1]-sum[i], sum[N]-sum[left+1]
  if abs(R1-S1) >= abs(R2-S2):
    R,S = R2, S2
  else:
    R,S = R1, S1

  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))

print(ans)

Fixed submission:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 
from itertools import accumulate


def diff(p,q,r,s):
  return abs(max(p,q,r,s) - min(p,q,r,s))


## input
N = int(sys.stdin.readline().rstrip())
An = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
sum = list(accumulate(An))


ans = sys.maxsize
li,ri = 1, 3
for i in range(2, N-1):
  while sum[li] < sum[i]-sum[li]:
    li += 1
  while sum[ri]-sum[i] < sum[N]-sum[ri]:
    ri += 1

  P1,Q1 = sum[li], sum[i]-sum[li]
  P2,Q2 = sum[li-1], sum[i]-sum[li-1]
  R1,S1 = sum[ri]-sum[i], sum[N]-sum[ri]
  R2,S2 = sum[ri-1]-sum[i], sum[N]-sum[ri-1]

  ans = min(ans, diff(P1,Q1,R1,S1), diff(P1,Q1,R2,S2), diff(P2,Q2,R1,S1), diff(P2,Q2,R2,S2))

print(ans)
Buggy python submission (verdict: Runtime Error):
# /user/bin/python
# -*- coding: utf-8 -*-
from matplotlib import pyplot


def solve(k):
  step = 1
  ret = 0
  mx = 9
  while k > 0:
    ret += step
    k -= 1
    if ret >= mx:
      step *= 10
      mx = mx*10 + 9
    print(ret)

k = int(input())
solve(k)

Fixed submission:
t = i = 1
k = int(input()) 
while k:
  if t < i / sum(map(int, list(str(i)))):
    i += 9 * t
    t *= 10
  else:
    print(i)
    i += t
    k -= 1
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
 

H,W,D = map(int, input().split())
An = {}
for i in range(H):
  s = list(map(int, input().split()))
  for j in range(W):
    An[s[j]] = [i,j]

Q = int(input())
ans = [0]*Q

for i in range(Q):
  l,r = map(int, input().split())
  while l < r:
    ans[i] += abs(An[l][0]-An[l+D][0]) + abs(An[l][1]-An[l+D][1])
    l += D

for j in range(Q):
  print(ans[j])

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
 

H,W,D = map(int, input().split())
An = [[0 for j in range(2)] for i in range(H*W+1)]
for i in range(H):
  s = list(map(int, input().split()))
  for j in range(W):
    An[s[j]] = [i,j]

Q = int(input())
csum = [0] * (H*W+1) # cumA[i] := i%D -> i に向かう累積和
for i in range(D+1,H*W+1):
  csum[i] = csum[i-D] + abs(An[i][0]-An[i-D][0]) + abs(An[i][1]-An[i-D][1])


ans = [0] * Q
for i in range(Q):
  l,r = map(int, input().split())
  ans[i] = csum[r] - csum[l]

for i in range(Q):
  print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

  for j in range(W,-1,-1):
    for i in range(H,-1,-1):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)


print(num_w - Cn[H][W] - 1)







Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(input()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

print(num_w - Cn[H][W] - 1)







Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
for _ in range(num_w):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

if Cn[H][W] < sys.maxsize:
  print(num_w - Cn[H][W])
else:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



Sn = str(input())
X,Y = map(int, input().split())

xyn = [0]
for c in Sn:
  if c == 'T':
    xyn.append(0)
  else:
    xyn[-1] += 1

Xn = xyn[2::2]
Yn = xyn[1::2]

dp_x = [xyn[0]]
for i in range(len(Xn)):
  dp_xn = []
  for j in dp_x:
    dp_xn = dp_xn + [j+Xn[i], j-Xn[i]]
  dp_x = dp_xn

dp_y = [0]
for i in range(len(Yn)):
  dp_yn = []
  for j in dp_y:
    dp_yn = dp_yn + [j+Yn[i], j-Yn[i]]
  dp_y = dp_yn

if X in dp_x and Y in dp_y:
  print("Yes")
else:
  print("No")


Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



Sn = str(input())
X,Y = map(int, input().split())

xyn = [0]
for c in Sn:
  if c == 'T':
    xyn.append(0)
  else:
    xyn[-1] += 1

Xn = xyn[2::2]
Yn = xyn[1::2]

dp_x = {xyn[0]}
for i in range(len(Xn)):
  dp_xn = {}
  for j in dp_x:
    dp_xn[j+Xn[i]] = 1
    dp_xn[j-Xn[i]] = 1
  dp_x = dp_xn

dp_y = {0}
for i in range(len(Yn)):
  dp_yn = {}
  for j in dp_y:
    dp_yn[j+Yn[i]] = 1
    dp_yn[j-Yn[i]] = 1
  dp_y = dp_yn


if X in dp_x and Y in dp_y:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


## input
N,C = map(int, input().split())
Cn = [[0 for j in range(10**5+1)] for i in range(C)]
An = [0 for j in range(10**5*2+1)]
for i in range(N):
  s,t,c = map(int, input().split())
  if Cn[c-1][s*2] == -1:
    An[s*2] += 1
  else:
    An[s*2-1] += 1
  An[t*2] -= 1

  Cn[c-1][s] += 1
  Cn[c-1][t] -= 1

for i in range(1,10**5*2+1):
  An[i] += An[i-1]

print(max(An))

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


## input
N,C = map(int, input().split())
Cn = [[0 for j in range(10**5+1)] for i in range(C)]
An = [0 for j in range(10**5+1)]
for i in range(N):
  s,t,c = map(int, input().split())
  if Cn[c-1][s] == -1:
    An[s] += 1
  else:
    An[s-1] += 1
  if Cn[c-1][t] == 1:
    An[t-1] -= 1
  else:
    An[t] -= 1    

  Cn[c-1][s] += 1
  Cn[c-1][t] -= 1

for i in range(1,10**5+1):
  An[i] += An[i-1]

print(max(An))
Buggy python submission (verdict: Runtime Error):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



An = [0 for _ in range(100001)]
for _ in range(int(input())):
  i = int(input())
  An[i] = (An[i]+1)%2

print(sum(An))

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
from collections import defaultdict


An = defaultdict()
for _ in range(int(input())):
  i = int(input())
  if i not in An:
    An[i] = 1
  else:
    An[i] += 1

ans = 0
for i in An:
  ans += An[i]%2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def main():
  N,M = map(int, input().split())
  route1 = []
  routeN = []
  for _ in range(M):
    ab = sorted(list(map(int, input().split())))
    if ab[0] == 1:
      route1.append(ab[1])
    elif ab[1] == N:
      routeN.append(ab[0])

  for i in route1:
    if i in routeN:
      return True
  return False

if __name__ == "__main__":
  if main():
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def main():
  N,M = map(int, input().split())
  route = [0 for _ in range(N+1)]

  for _ in range(M):
    a,b = map(int, input().split())
    if a == 1:
      route[b] += 1
    elif b == N:
      route[a] += 1

  if max(route) >= 2:
    return True
  else:
    return False


if __name__ == "__main__":
  if main():
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
import numpy as np


N = int(input())
An = list(map(int, input().split()))
sm = [0, sum(An)]

ans = abs(An[0] - sum(An[1:]))
for i in range(N-1):
  sm[0] += An[i]
  sm[1] -= An[i]
  ans = min(ans, abs(sm[0]-sm[1]))
print(ans)

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))
sm = [0, sum(An)]

ans = abs(An[0] - sum(An[1:]))
for i in range(N-1):
  sm[0] += An[i]
  sm[1] -= An[i]
  ans = min(ans, abs(sm[0]-sm[1]))
print(ans)

Buggy python submission (verdict: Runtime Error):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
import numpy as np


N = int(input())
An = np.asarray(list(map(int, input().split())))
cumsum = np.cumsum(An)
sm = np.sum(An)

ans = 10**14+1
for i in range(N-1):
  ans = min(ans, abs(sm-2*cumsum[i]))
print(ans)

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))
sm = [0, sum(An)]

ans = abs(An[0] - sum(An[1:]))
for i in range(N-1):
  sm[0] += An[i]
  sm[1] -= An[i]
  ans = min(ans, abs(sm[0]-sm[1]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))
Bn = []
for a in An:
  Bn = [a] + Bn[::-1]

for b in Bn:
  print(b,end=" ")

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math


N = int(input())
An = list(map(int, input().split()))

if N%2 == 0:
  Bn = An[-1::-2] + An[0::2]
else:
  Bn = An[-1::-2] + An[1::2]

for b in Bn:
  print(b,end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



D = 10**9+7

def main():
  NM = sorted(list(map(int, input().split())))
  if NM[1]-NM[0] > 1:
    return 0
  elif NM[0]==NM[1]:
    ret = 2*(math.factorial(NM[0])**2) % D
    return ret
  else:
    ret = math.factorial(NM[0])*math.factorial(NM[1])
    return ret

if __name__ == "__main__":
  print(main())

Fixed submission:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



D = 10**9+7

def main():
  NM = sorted(list(map(int, input().split())))
  if NM[1]-NM[0] > 1:
    return 0
  elif NM[0]==NM[1]:
    ret = 2*(math.factorial(NM[0])**2) % D
    return ret
  else:
    ret = math.factorial(NM[0])*math.factorial(NM[1]) % D
    return ret

if __name__ == "__main__":
  print(main())
Buggy python submission (verdict: Time Limit Exceeded):


a,b,x = map(int, input().split())

ret = 0
for i in range(a,b+1):
  if i%x==0:
    ret += 1
print(ret)  

Fixed submission:
a,b,x = map(int, input().split())
print(b//x-(a-1)//x)