Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
for i in range(N-K+1):
    check = 0
    for j in range(K):
        check += dices[i+j]
    list.append(check)
print((max(list)+K)/2)

Fixed submission:
N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
check=0
for i in range(K):
    check+=dices[i]
list.append(check)
for j in range(N-K):
    check -= dices[j]
    check += dices[j+K]
    list.append(check)    
print((max(list)+K)/2)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
dices = list(map(int,input().split()))
ans = 0
for i in range(N-K+1):
    check = 0
    for j in range(K):
        check += dices[i+j]
    if check > ans:
        ans = check
print((ans+K)/2)         

Fixed submission:
N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
check=0
for i in range(K):
    check+=dices[i]
list.append(check)
for j in range(N-K):
    check -= dices[j]
    check += dices[j+K]
    list.append(check)    
print((max(list)+K)/2)
Buggy python submission (verdict: Time Limit Exceeded):
import math
N, P = map(int,input().split())
if N == 1:
    print(P)
else:
    l = 1/N
    check = math.ceil(P**l)
    while check >1:
        if P%(check**N) == 0:
            break
        check-=1
    print(check)

Fixed submission:
import math
N, P = map(int,input().split())
if N == 1:
    print(P)
else:
    l = 1/N
    check = round(P**l)
    while check >1:
        if P%(check**N) == 0:
            break
        check-=1
    print(check)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = round(np.median(numbers))
numbers-= b
number = np.abs(numbers)
print(number.sum())

Fixed submission:
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = int(round(np.median(numbers)))
numbers-= b
number = np.abs(numbers)
print(number.sum())

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = round(np.median(numbers))
numbers-= b
print(numbers.sum())


Fixed submission:
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = int(round(np.median(numbers)))
numbers-= b
number = np.abs(numbers)
print(number.sum())
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(1,3501):
    h_pro = Fraction(1,h)
    for n in range(1,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()

Fixed submission:
from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(max(point),3501):
    h_pro = Fraction(1,h)
    check = ans - h_pro
    target = [math.floor(4*h-N/N*h),h]
    for n in range(h,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(max(point),3501):
    h_pro = Fraction(1,h)
    check = ans - h_pro
    target = [math.floor(4*h-N/N*h),h]
    for n in range(h,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()

Fixed submission:
from fractions import Fraction
import math
N = int(input())
ans = Fraction(4,N)
point = [1,math.floor(N/4)]
for h in range(max(point),3501):
    h_pro = Fraction(1,h)
    check = ans - h_pro
    target = [math.floor(4*h-N/N*h),h]
    for n in range(h,3501):
        check = ans - h_pro
        n_pro = Fraction(1,n)
        check -= n_pro
        if type(check) == "int":
            if check ==1:
                print(h, end=" ")
                print(n, end=" ")
                print(1)
                exit()
        elif check.numerator == 1:
            print(h, end=" ")
            print(n, end=" ")
            print(check.denominator)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()

push(q, [xyn[0][1], xyn[0][2]])
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m
  if yy < y:
    uni.merge(nn, n)
    while q:
      yy, nn = pop(q)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, [yy, nn])
        break
  else:
    push(q, [y, n])
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])


Fixed submission:
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()
x, y, n = xyn[0]
push(q, (y << 20) + n)
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m >> 20, m % (1 << 20)
  if yy < y:
    uni.merge(nn, n)
    while q:
      p = pop(q)
      yy, nn = p >> 20, p % (1 << 20)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, (yy << 20) + nn)
        break
  else:
    push(q, (y << 20) + n)
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])
Buggy python submission (verdict: Time Limit Exceeded):
# test
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xにnを加える
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)

for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.update(p, x)
  else:
    _, l, r = q
    print(bit.getV(r - 1) - bit.getV(l - 1))

Fixed submission:
# test
class BIT:
  ini = 0
  def __init__(s, num):
    s.N = 1
    while s.N <= num:
      s.N *= 2
    s.T = [s.ini] * s.N
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, n): # xにnを加える
    k = x + 1
    s.T[k - 1] += n
    k += k & -k
    while k <= s.N:
      s.T[k - 1] += n
      k += k & -k
  def getV(s, x): # xまでの和(x含む)
    if x < 0: return 0
    x += 1
    ans = s.T[x - 1]
    x -= x & -x
    while x != 0:
      ans += s.T[x - 1]
      x -= x & -x
    return ans

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]
  
bit = BIT(N)
bit.set(a)

for q in Query:
  if q[0] == 0:
    _, p, x = q
    bit.update(p, x)
  else:
    _, l, r = q
    print(bit.getV(r - 1) - bit.getV(l - 1))
Buggy python submission (verdict: Time Limit Exceeded):
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
          q.put([hh, ww])
          T[hh][ww] = k
      for i in range(-2, 3):
        for j in range(-2, 3):
          hh = h + i
          ww = w + j
          if hh < 0: continue
          if hh > H: continue
          if ww < 0: continue
          if ww > W:continue
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            T[hh][ww] = k + 1

    return T, k


H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])

Fixed submission:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    D = [[S[0], S[1]]]
    while True:
      while not q.empty():
        h, w = q.get()
        k = T[h][w]
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
          hh = h + i
          ww = w + j
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            D.append([hh, ww])
            T[hh][ww] = k
      if len(D) == 0: break
      ND = []
      for h, w in D:
        for i in range(-2, 3):
          for j in range(-2, 3):
            hh = h + i
            ww = w + j
            if hh < 0: continue
            if hh > H: continue
            if ww < 0: continue
            if ww > W:continue
            if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k + 1):
              q.put([hh, ww])
              ND.append([hh, ww])
              T[hh][ww] = k + 1
      D = ND

    return T, k


H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])
Buggy python submission (verdict: Time Limit Exceeded):
H, W, M = list(map(int, input().split())) 
hw = [list(map(int, input().split())) for _ in range(M)]

LH = [0] * H
LW = [0] * W

R = {}
for i in range(M):
  h = hw[i][0] - 1
  w = hw[i][1] - 1
  LH[h] += 1
  LW[w] += 1
  if h in R:
    R[h][w] = 1
  else:
    R[h] = {}
    R[h][w] = 1

mah = max(LH)
maw = max(LW)

ans = mah + maw
for i in range(H):
  if LH[i] != mah: continue
  for j in range(W):
    if LW[j] != maw: continue
    if i not in R:
      break
    if j not in R[i]:
      break
  else:
    continue
  break
else:
  print(ans - 1)
  exit()

print(ans)


Fixed submission:
H, W, M = list(map(int, input().split())) 
hw = [list(map(int, input().split())) for _ in range(M)]

LH = [0] * H
LW = [0] * W

R = {}
for i in range(M):
  h = hw[i][0] - 1
  w = hw[i][1] - 1
  LH[h] += 1
  LW[w] += 1
  if h in R:
    R[h][w] = 1
  else:
    R[h] = {}
    R[h][w] = 1

mah = max(LH)
maw = max(LW)
DH = []
DW = []

for i in range(H):
  if LH[i] == mah:
    DH.append(i)
for i in range(W):
  if LW[i] == maw:
    DW.append(i)

ans = mah + maw
for i in DH:
  if LH[i] != mah: continue
  for j in DW:
    if LW[j] != maw: continue
    if i not in R:
      break
    if j not in R[i]:
      break
  else:
    continue
  break
else:
  print(ans - 1)
  exit()

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

if K % 7 == 0:
  K //= 7
k = 1
cnt = 1
while True:
  if k % K == 0:
    break
  k = (k * 10 + 1) % K
  cnt += 1

print(cnt)

Fixed submission:
K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

if K % 7 == 0:
  K //= 7
k = 1
cnt = 1
for i in range(10 ** 8):
  if k % K == 0:
    break
  k = (k * 10 + 1) % K
  cnt += 1
else:
  print(-1)
  exit()

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

k = 7
cnt = 1
while True:
  if k % K == 0:
    break
  k = (k * 10 + 7) % K
  cnt += 1

print(cnt)

Fixed submission:
K = int(input())

if K % 2 == 0:
  print(-1)
  exit()

if K % 7 == 0:
  K //= 7
k = 1
cnt = 1
for i in range(10 ** 8):
  if k % K == 0:
    break
  k = (k * 10 + 1) % K
  cnt += 1
else:
  print(-1)
  exit()

print(cnt)
Buggy python submission (verdict: Runtime Error):
T = int(input())

def hakidasi(L):
  n = len(bin(max(L))) - 2
  k, end = 0, len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, end):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(end):
      if j == k - 1: continue
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def judge(L, x):
  n = len(bin(max(L))) - 2
  m = len(L)
  for i in range(m):
    a = len(bin(x))
    b = len(bin(L[i]))
    if a == b:
      x ^= L[i]
    elif a > b:
      return False
    if x == 0:
      return True
  return False

def main():
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  U = 60
  
  L = []
  for i in range(N - 1, -1, -1):
    n = int(S[i])
    if n == 0:
      L.append(A[i])
      L = hakidasi(L)
      if L[-1] == 0:
        L.pop()
    else:
      m = judge(L, A[i])
      if m == False:
        return 1
  return 0

for i in range(T):
  print(main())

Fixed submission:
T = int(input())

def hakidasi(L):
  n = len(bin(max(L))) - 2
  k, end = 0, len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, end):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(end):
      if j == k - 1: continue
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def judge(L, x):
  if L == []:
    return False
  n = len(bin(max(L))) - 2
  m = len(L)
  for i in range(m):
    a = len(bin(x))
    b = len(bin(L[i]))
    if a == b:
      x ^= L[i]
    elif a > b:
      return False
    if x == 0:
      return True
  return False

def main():
  N = int(input())
  A = list(map(int, input().split()))
  S = input()
  U = 60
  
  L = []
  for i in range(N - 1, -1, -1):
    if A[i] == 0:
      continue
    n = int(S[i])
    if n == 0:
      L.append(A[i])
      L = hakidasi(L)
      if L[-1] == 0:
        L.pop()
    else:
      m = judge(L, A[i])
      if m == False:
        return 1
  return 0

for i in range(T):
  print(main())
Buggy python submission (verdict: Runtime Error):
class Dijkstra:
  R = {}
  import heapq
  pop = heapq.heappop
  push = heapq.heappush
  
  def __init__(s, N):
    s.N = N

  def add(s, a, b, x):
    if a not in s.R: s.R[a] = {b: x}
    else: s.R[a][b] = x
    if b not in s.R: s.R[b] = {a: x}
    else: s.R[b][a] = x

  def exe(s, start):
    D = [-1] * s.N 
    q  = []
    s.push(q, [0, start])
    cnt = 0
    while cnt < s.N:
      if len(q) == 0:
        return None
      d, x = s.pop(q)
      if D[x] != -1: continue
      D[x] = d
      cnt += 1
      for i in s.R[x]:
        if D[i] != -1: continue
        j = s.R[x][i]
        s.push(q, [d + j, i])
    return D


N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

D = Dijkstra(N)

for a, b in AB:
  D.add(a - 1, b - 1, 1)

L = D.exe(0)

if L == None:
  print("No")
  exit()

R = {}

for i in range(N):
  if L[i] in R:
    R[L[i]].append(i)
  else:
    R[L[i]] = [i]

Ans = [0] * N
for i in R.keys():
  for j in R[i]:
    for k in D.R[j].keys():
      if L[k] == L[j] + 1:
        Ans[k] = j + 1

print("Yes")
for i in range(1, N):
  print(Ans[i])

Fixed submission:
class Dijkstra:
  R = {}
  import heapq
  pop = heapq.heappop
  push = heapq.heappush
  
  def __init__(s, N):
    s.N = N

  def add(s, a, b, x):
    if a not in s.R: s.R[a] = {b: x}
    else: s.R[a][b] = x
    if b not in s.R: s.R[b] = {a: x}
    else: s.R[b][a] = x

  def exe(s, start):
    D = [-1] * s.N 
    q  = []
    s.push(q, [0, start])
    cnt = 0
    while cnt < s.N:
      if len(q) == 0:
        return None
      d, x = s.pop(q)
      if D[x] != -1: continue
      D[x] = d
      cnt += 1
      for i in s.R[x]:
        if D[i] != -1: continue
        j = s.R[x][i]
        s.push(q, [d + j, i])
    return D


N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

D = Dijkstra(N)

for a, b in AB:
  D.add(a - 1, b - 1, 1)

L = D.exe(0)

if L == None:
  print("No")
  exit()

R = {}

for i in range(N):
  if L[i] in R:
    R[L[i]].append(i)
  else:
    R[L[i]] = [i]

Ans = [0] * N
for i in R.keys():
  for j in R[i]:
    for k in D.R[j].keys():
      if L[k] == L[j] + 1:
        Ans[k] = j + 1

print("Yes")
for i in range(1, N):
  print(Ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
S = list(map(int, list(input())))
N = len(S)
MOD = 2019
DP = [0] * MOD
DP[0] = 1

t = 0

for i in range(N):
  k = S[-1 - i]
  t = (t + k * 10 ** i) % MOD
  DP[t] += 1

ans = 0
for i in range(MOD):
  n = DP[i]
  ans += (n * (n - 1)) // 2

print(ans)

Fixed submission:
S = list(map(int, list(input())))
N = len(S)
MOD = 2019
DP = [0] * MOD
DP[0] = 1

t = 0
p = 1
for i in range(N):
  k = S[-1 - i]
  t = (t + k * p) % MOD
  DP[t] += 1
  p = p * 10 % MOD

ans = 0
for i in range(MOD):
  n = DP[i]
  ans += (n * (n - 1)) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
  n, x = D[i]
  t = i + 1
  for j in range(t + 1):
    l = j
    r = t - j
    rr = N - 1 - r
    if l != 0:
      DP[l][r] = DP[l - 1][r] + abs(n - l + 1) * x
    if r != 0:
      DP[l][r] = max(DP[l][r], DP[l][r - 1] + abs(rr + 1 - n) * x)

ans = 0
for i in range(N + 1):
  ans = max(ans, DP[i][N - i])
print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
  n, x = D[i]
  t = i + 1
  for j in range(t + 1):
    l = j
    r = t - j
    rr = N - 1 - r
    if l != 0:
      DP[l][r] = DP[l - 1][r] + abs(n - l + 1) * x
    if r != 0:
      DP[l][r] = max(DP[l][r], DP[l][r - 1] + abs(rr + 1 - n) * x)

ans = 0
for i in range(N + 1):
  ans = max(ans, DP[i][N - i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    if cnt == 2: t = 1
    else: t = 2
    for i in range(cnt, last + 1, t):
      if x % i == 0:
        x //= i
        p[i] = 1
        if cnt == 2: cnt = 3
        else: cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

if N == 2:
  print(1)
  exit()

ans = 1
for i in P.keys():
  ans *= P[i] + 1
ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * n)
    n *= i


for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)


Fixed submission:
import math
def prime(x):
  L = []
  last = math.floor(x ** 0.5) 
  for i in range(1, last + 1):
    if x % i == 0:
      L.append(i)
      if x // i != i:
        L.append(x // i)
  return L

N = int(input())

if N == 2:
  print(1)
  exit()

L = prime(N - 1)

ans = len(L) - 1

D = prime(N)

for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
S = list(input())
Q = int(input())
Qu= [list(input().split()) for _ in range(Q)]

r = 0

B = []
A = []

for i in range(Q):
  if int(Qu[i][0]) == 1:
    r = 1 - r
  else:
    F = int(Qu[i][1])
    C = Qu[i][2]
    F -= 1
    if F == r:
      B.append(C)
    else:
      A.append(C)

if r == 0:
  B.reverse()
  print("".join(B + S + A))
else:
  A.reverse()
  print("".join(A + S.reverse() + B))


Fixed submission:
S = list(input())
Q = int(input())
Qu= [list(input().split()) for _ in range(Q)]

r = 0

B = []
A = []

for i in range(Q):
  if int(Qu[i][0]) == 1:
    r = 1 - r
  else:
    F = int(Qu[i][1])
    C = Qu[i][2]
    F -= 1
    if F == r:
      B.append(C)
    else:
      A.append(C)

if r == 0:
  B.reverse()
  print("".join(B + S + A))
else:
  A.reverse()
  S.reverse()
  print("".join(A + S + B))