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

Fixed submission:
import bisect

N = int(input())
A = sorted(map(int,input().split()))

i = bisect.bisect_left(A, 0)
j = bisect.bisect_right(A, 0)
if i == j:
    if i == 0:
        negatives = A[:1]
        positives = A[1:]
    elif i == N:
        negatives = A[:-1]
        positives = A[-1:]
    else:
        negatives = A[:i]
        positives = A[i:]

else:
    m = max((i+j)//2, 1)
    negatives = A[:m]
    positives = A[m:]


score = sum(positives) - sum(negatives)
print(score)

def it():

    def balanced(pos, neg):
        y = neg.pop()
        x = pos.pop()
        yield (x,y)
        y = x-y
        while pos and neg:
            x = neg.pop()
            yield (x,y)
            y = x-y
            x = pos.pop()
            yield (x,y)
            y = x-y

    if len(positives) < len(negatives):

        x = positives.pop()

        while len(positives)+1 < len(negatives):
            y = negatives.pop()
            yield (x,y)
            x -= y
        positives.append(x)
    elif len(positives) > len(negatives):
        x = negatives.pop()

        while len(negatives)+1 < len(positives):
            y = positives.pop()
            yield (x,y)
            x -= y
        negatives.append(x)

    for x,y in balanced(positives, negatives):
        yield x,y


for x,y in it():
    print(x,y)

Buggy submission (verdict: Runtime Error):
from bisect import bisect

def solve():
    N = int(input())
    A = sorted(map(int,input().split()))
    if N == 2:
        res = [(max(A),min(A))]
        s = max(A)-min(A)
        return s, res

    if A[0] >= 0:
        res = []
        x = A[0]
        for a in A[1:-1]:
            res.append((x,a))
            x -= a
        res.append((A[-1],x))
        x = A[-1]-x
        return (x,res)
    if A[-1] <= 0:
        res = []
        x = A[-1]
        for a in A[-1]:
            res.append((x,a))
            x -= a
        return (x,res)

    res = []
    p = bisect(A,0)-1
    x = A[p]
    for a in A[p+1:N-1]:
        res.append((x,a))
        x -= a
    res.append((A[-1],x))
    x = A[-1]-x
    for a in A[:p]:
        res.append((x,a))
        x -= a
    return (x,res)



s,res = solve()
print(s)
print('\n'.join(f'{a} {b}' for a,b in res))

Buggy submission (verdict: Runtime Error):
from bisect import bisect

def solve():
    N = int(input())
    A = sorted(map(int,input().split()))


    if A[0] >= 0:
        res = []
        x = A[0]
        for a in A[1:-1]:
            res.append((x,a))
            x -= a
        res.append((A[-1],x))
        x = A[-1]-x
        return (x,res)
    if A[-1] <= 0:
        res = []
        x = A[-1]
        for a in A[-1]:
            res.append((x,a))
            x -= a
        return (x,res)

    res = []
    p = bisect(A,0)-1
    x = A[p]
    for a in A[p+1:N-1]:
        res.append((x,a))
        x -= a
    res.append((A[-1],x))
    x = A[-1]-x
    for a in A[:p]:
        res.append((x,a))
        x -= a
    return (x,res)



s,res = solve()
print(s)
print('\n'.join(f'{a} {b}' for a,b in res))
Problem p03046 (python)

Fixed submission:
from functools import reduce
from operator import xor
from itertools import chain

def main():
    M,K = map(int,input().split())

    if K >= 2**M:
        print(-1)
        return

    if M >= 2:
        def it():
            for i in reversed(range(2**M)):
                if i != K:
                    yield i
            yield K
            for i in range(2**M):
                if i != K:
                    yield i
            yield K
        print(*it())
    elif M == 1:
        if K == 0:
            print(0,0,1,1)
        else:
            print(-1)
    else:
        print(0, 0)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from functools import reduce
from operator import xor
from itertools import chain

def main():
    M,K = map(int,input().split())

    if K == 0:
        def it():
            for i in range(2**M):
                yield i
                yield i
        print(*it())
        return

    # check
    r = reduce(xor, chain(range(2**M),(K,)))

    if r == K:
        print(*reversed(range(2**M)),K,*range(2**M),K)
    else:
        print(-1)

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

Fixed submission:
from itertools import tee,count
N = int(input())
H0,H1,H2 = tee(map(int,input().split()), 3)
next(H2)

dp = [0, abs(next(H2)-next(H1))]

for i,h0,h1,h2 in zip(count(1), H0,H1,H2):
  dp.append(min(dp[i]+abs(h2-h1), dp[i-1] + abs(h2-h0)))

print(dp[-1])

Buggy submission (verdict: Runtime Error):
import numpy as np
N,K = map(int,input().split())
H = np.array(list(map(int,input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1,N):
  s = max(i-K,0)
  dp[i] = np.min(dp[s:i]+np.abs(H[s:i]-H[i]))

print(dp[-1])
Problem p03161 (python)

Fixed submission:
N,K = map(int,input().split())
H = tuple(map(int,input().split()))

dp = [0]

for i in range(1,N):
  h = H[i]
  dp.append(min(dp[j]+abs(H[j]-h) for j in range(max(i-K,0),i)))

print(dp[-1])

Buggy submission (verdict: Runtime Error):

N,K = map(int,input().split())
H = list(map(int,input().split()))

dp = []

for i in range(N):
  h = H[i]
  dp.append(min((dp[-j-1]+abs(h-H[i-j-1]) for j in range(min(i,K))), default=0))

print(dp[-1])
Problem p03219 (python)

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

Buggy submission (verdict: Runtime Error):
x,y = map(int(input().split()))
print(x+y//2)
Problem p03241 (python)

Fixed submission:
from itertools import product
from collections import Counter
from functools import reduce
import operator
num_product = lambda it: reduce(operator.mul,it,1)

# 素因数分解
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n



N,M = map(int,input().split())
P = tuple(tuple(p**i for i in range(d+1)) for p,d in Counter(prime_factors(M)).items())
def it():
  for nums in product(*P):
    t = num_product(nums)
    yield t
print(max(t for t in it() if t*N <= M))

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
gcd = m//n
while n*gcd != m:
  gcd = M//n
  n = 1 + (M-1)//gcd
print(gcd)

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
gcd = m//n
while n*gcd != m:
  n = 1 + (M-1)//gcd
  gcd = M//n
print(gcd)
Problem p03261 (python)

Fixed submission:
from itertools import tee
N = int(input())
w0, w1 = tee((input() for _ in range(N)), 2)

words = {next(w1)}
flag = 'Yes'
for a,b in zip(w0,w1):
  if a[-1] != b[0] or b in words:
    flag = 'No'
  words.add(b)

print(flag)

Buggy submission (verdict: Runtime Error):
from itertools import tee
N = int(input())
w0, w1 = tee((int(input()) for _ in range(N)), 2)
next(w1)
for a,b in zip(w0,w1):
  if a[-1] != b[0]:
    print('No')
    break
else:
  print('Yes')
Problem p03312 (python)

Fixed submission:
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

def solve(x):
  L = h(0,x)+h(x,N)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-1)))

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def h(i,j):
  ci,cj = C[i],C[j]
  k = bisect(C, (ci+cj)//2, lo=i+1,hi=j)
  _,a,b = min((abs(ci+cj-2*c),cj-c,c-ci) for c in (C[k-1],C[k]))
  return a,b

def solve(x):
  L = h(0,x)+h(x,N)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-2)))

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from bisect import bisect

N = int(input())
C = [0]+list(accumulate(map(int,input().split())))

def solve(x):
  def h(i,j):
    m = (C[j]+C[i])//2
    k = bisect(C, m, lo=i+1,hi=j)

    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
    return a,b

  L = h(0,x)+h(x,N)
  return max(L)-min(L)

print(min(solve(i) for i in range(2,N-2)))

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
C = [0]+list(accumulate(A))

def helper(i,j):
  m = (C[j]+C[i])/2
  k = bisect(C, m, lo=i,hi=j)
  if k == i:
    k += 1
  elif k == j:
    k -= 1

  if k > 0:
    _,a,b = min((abs(m-C[x]),C[x]-C[i],C[j]-C[x]) for x in (k-1,k))
  else:
    a,b = C[k]-C[i],C[j]-C[k]

  return a,b

best = float('inf')

for i in range(2,N-1):
  L = (*helper(0,i),*helper(i,N))
  best = min(best,max(L)-min(L))

print(best)
Problem p03333 (python)

Fixed submission:
N = int(input())

intervals = list(tuple(map(int,input().split())) for _ in range(N))

L = sorted(((l,i) for i,(l,r) in enumerate(intervals)))
R = sorted(((r,i) for i,(l,r) in enumerate(intervals)), reverse=True)

def helper(L,R,turn):
  used = [False]*(N+1)
  used[N] = True

  x = 0
  cost = 0
  while True:
    A = [L,None,R][turn+1]

    i = N
    while used[i]:
      y,i = A.pop()

    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in [-1,1]))

Buggy submission (verdict: Runtime Error):
N = int(input())
L,R = [None]*N,[None]*N
for i in range(N):
  L[i],R[i] = map(int,input().split())
L.sort(reverse=True)
R.sort()

def it():
  for l,r in zip(L,R):
    if r < l
      yield 2*(l-r)
    else:
      return

print(sum(it()))
Problem p03334 (python)

Fixed submission:
from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  if D%2 == 1:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
    grid[:,1::2] = ~grid[:,1::2]
  elif D%4 == 2:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
  else:
    M = (N-1)//2+1
    D //= 4
    g = helper(M, D)
    grid = np.zeros((2*M,2*M),dtype=bool)
    grid[::2,::2] = g
    grid[1::2,::2] = g
    grid[::2,1::2] = g
    grid[1::2,1::2] = g
    grid = grid[:N,:N]
  return grid


N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N*2,D1)
g2 = helper(N*2,D2)
ans = g1&g2


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)

Buggy submission (verdict: Runtime Error):
from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  if D%2 == 1:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
    grid[:,1::2] = ~grid[:,1::2]
  elif D%4 == 2:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
  else:
    M = (N-1)//2+1
    D //= 4
    g = helper(M, D)
    grid = np.zeros((M,M),dtype=bool)
    grid[::2,::2] = g
    grid[1::2,::2] = g
    grid[::2,1::2] = g
    grid[1::2,1::2] = g
    grid = grid[:N,:N]
  return grid


N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N*2,D1)
g2 = helper(N*2,D2)
ans = g1&g2


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
Problem p03561 (python)

Fixed submission:
from itertools import chain,repeat
K,N = map(int,input().split())

def solve():

  if K % 2 == 0:
    return ' '.join(map(str, chain((K//2,),repeat(K,N-1))))
  else:
    seq = [K//2+1]*N
    d = N//2
    for _ in range(d):
      if seq[-1] == 1:
        seq.pop()
      else:
        seq[-1] -= 1
        seq.extend(repeat(K,N-len(seq)))
    return ' '.join(map(str, seq))

def naive():
  from itertools import product
  s = sorted(chain.from_iterable(product(range(1,K+1),repeat=i) for i in range(1,N+1)))
  return ' '.join(map(str, s[(len(s)-1)//2]))

print(solve())
# print(naive())

Buggy submission (verdict: Runtime Error):
from itertools import chain,repeat
K,N = map(int,input().split())

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d+1):
    seq = dec(seq)
  print(' '.join(map(str, seq)))

Buggy submission (verdict: Runtime Error):
from itertools import chain,repeat
K,N = map(int,input().split())

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d):
    seq = dec(seq)
  print(' '.join(map(str, seq)))
Problem p03566 (python)

Fixed submission:
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):

  ndp = [None]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi = min(len(dp)-1,vf+t)
    while vi >= 0 and dp[vi] is None:
      vi -= 1

    if vi < max(0,vf-t):
      ndp[vf] = None
    else:
      vp = (vf+t+vi)/2
      ndp[vf] = dp[vi] + 2*vp*vp-vf*vf-vi*vi - 2*max(0,vp-v_max)**2
  dp = ndp
 
print(dp[0]/8)

Buggy submission (verdict: Runtime Error):
from itertools import chain
 
double = lambda c: int(c)*2
 
N = int(input())
T = tuple(map(double,input().split()))
V = tuple(map(double,input().split()))
 
dp = [0]
 
for t,v_max,vf_max in zip(T,V,chain(V[1:],(0,))):
  ndp = [0]*(min(vf_max,v_max)+1)
  
  for vf in range(len(ndp)):
    vi_min = max(0,vf-t)
    vi_max = min(v_max,vf+t)
    def it():
      for vi,d in enumerate(dp[vi_min:vi_max+1], start=vi_min):
        vp = (t+vi+vf)/2
        yield d + 2*vp*vp-vf*vf-vi*vi - 2*(max(0,vp-v_max))**2
    ndp[vf] = max(it())
  
  dp = ndp
 
print(dp[0]/8)
Problem p03567 (python)

Fixed submission:
print('Yes' if 'AC' in input() else 'No')

Buggy submission (verdict: Runtime Error):
print(‘Yes’ if ‘AC’ in input() else ‘No’)
Problem p03577 (python)

Fixed submission:
print(input()[:-8])

Buggy submission (verdict: Runtime Error):
a,b,c = map(int,input().split())

L = [[0] for _ in range(a)] + [[1] for _ in range(b)] + [[2] for _ in range(c)]
while len(L) > 1:
  L[0] += L.pop()
  L.sort()
print(''.join(('a','b','c')[i] for i in L[0]))
Problem p03594 (python)

Fixed submission:
h,w,d = map(int,input().split())
c = ('R','Y','G','B')

from itertools import product
for i in range(h):
  line = []
  for j in range(w):
    x = (i-j)%(2*d) >= d
    y = (i+j)%(2*d) >= d
    line.append(c[2*x+y])
  print(''.join(line))

Buggy submission (verdict: Runtime Error):
h,w,d = map(int,input().split())
d //= 2
c1 = ('R','Y')
c2 = ('G','B')

l1 = []
i = 0
m = 0
while i < w:
  l1.append(c1[m])
  i+=1
  if i%d == 0:
    m = 1-m

l2 = []
i = 0
m = 0
while i < w:
  l2.append(c2[m])
  i+=1
  if i%d == 0:
    m = 1-m

c1 = ''.join(l1)
c2 = ''.join(l2)

for i in range(h):
  if i%(2*d) < d:
    print(c1)
  else:
    print(c2)
Problem p03601 (python)

Fixed submission:
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

salt = sorted(salt)

from bisect import bisect_left



bs,bw = 0,min(a,b)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  if i >= len(water):
    break
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)

Buggy submission (verdict: Runtime Error):
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)

Buggy submission (verdict: Runtime Error):
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+1),range(f//(100*b)+1)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+1),range(f//d+1)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)
Problem p03609 (python)

Fixed submission:
import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))

Buggy submission (verdict: Runtime Error):
import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))
os.write(1,' '.join(str(a),str(b)).encode())
Problem p03627 (python)

Fixed submission:
n = int(input())
s = set()
q = [0,0]
import heapq as hq
for a in map(int, input().split()):
  if a > q[0]:
    try:
      s.remove(a)
      hq.heapreplace(q, a)
    except:
      s.add(a)

print(q[0]*q[1])

Buggy submission (verdict: Runtime Error):
n = int(input())
s = set()
q = [0,0]
import heaps as hq
for a in map(int, input().split()):
  if a > q[0]:
    if a in s:
      del s[a]
      hq.heapreplace(q, a)
    else:
      s.add(a)

print(q[0]*q[1])
Problem p03651 (python)

Fixed submission:
from fractions import gcd

N,K = map(int,input().split())
A = list(map(int,input().split()))

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Buggy submission (verdict: Runtime Error):
from math import gcd

N,K = map(int,input().split())
A = list(map(int,input().split()))

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
Problem p03703 (python)

Fixed submission:
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from bisect import bisect

N,K = map(int, input().split())

A = [int(input()) for i in range(N)]

t = 0
B = [t]
for a in A:
  t += a - K
  B.append(t)

temp = sorted(B)
C = [bisect(temp, b) for b in B]

result = 0
bit = BinaryIndexedTree(N+1)

for c in C:
  result += bit.sum(c)
  bit.add(c,1)

print(result)

Buggy submission (verdict: Runtime Error):
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from itertools import accumulate,repeat

N,K = map(int, input().split())

B = [0] + [sa-sk for sa,sk in zip(accumulate(int(input())), accumulate(repeat(K, N)))]

lookup = dict(((b,i+1) for i,b in enumerate(sorted(B))))

result = 0
bit = BinaryIndexedTree(N+1)

for b in B:
  c = lookup[b]
  result += bit.sum(c)
  bit.add(c,1)

print(result)
Problem p03716 (python)

Fixed submission:
from heapq import *

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A_indexed[N:])
  selected_right_set = set(temp[:N])
  unselected_right = temp[N:] # min heap
  del temp
  r_score = sum(map(lambda x: x[0], selected_right_set))

  yield l_score,r_score

  for i in range(N, 2*N):
    a = A[i]
    # left 使うものを減らす, right 使うものを増やす
    if selected_left[0] < a:
      l_score -= heapreplace(selected_left, a)
      l_score += a
      
    if (a,i) in selected_right_set:
      r_score -= a
      selected_right_set.remove((a,i))

      n_element = heappop(unselected_right)
      while n_element[1] <= i:
        n_element = heappop(unselected_right)
      selected_right_set.add(n_element)
      r_score += n_element[0]

    yield l_score,r_score

# print(list(scores()))
print(max(map(lambda x: x[0]-x[1],scores())))

Buggy submission (verdict: Runtime Error):
from heapq import *
from collections import Counter

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A[N:])
  selected_right = Counter(temp[:N])
  unselected_right_counter = Counter(temp[N:])
  unselected_right = list(unselected_right_counter.keys()) # min heap
  heapify(unselected_right)


  r_score = sum(selected_right)

  yield l_score-r_score

  for i,a in enumerate(A[N:2*N]):
    # left 使うものを減らす, right 使うものを増やす
    l_score -= heappushpop(selected_left, a)
    l_score += a
      
    if selected_right[a] > 0:
      r_score -= a
      selected_right[a] -= 1

      x = unselected_right[0]
      while unselected_right_counter[x] == 0:
        del unselected_right_counter[x]
        x = heappop(unselected_right)

      unselected_right_counter[x] -= 1
      selected_right[x] += 1
      r_score += x
    else:
      del selected_right[a]
      unselected_right_counter[a] -= 1

    yield l_score-r_score

print(max(scores()))
Problem p03717 (python)

Fixed submission:
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j)+1:
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

Buggy submission (verdict: Runtime Error):
x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,c in enumerate(map(sum,zip(x_sum,y_sum))):
    c %= MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append(2*s%MOD)
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j):
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        y_sum[j] %= MOD
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
  s %= MOD

print(s)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  dp.update(((i,pk),s%MOD) for i,s in enumerate(map(sum, zip(x_sum,y_sum))))

  for i in range(pk):
    x_sum[i] += dp[i,pk]
  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3

  removes = [(i,j) for i,j in dp.keys()
            if any(x != (l<=i)+(l<=j)+1 for l,x in Q[k])]

  for i,j in removes:
    c = dp[i,j]
    del dp[i,j]
    x_sum[i] -= c
    y_sum[j] -= c
    s -= c

  for i,j in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)
Problem p03733 (python)

Fixed submission:
f=lambda:map(int,input().split())
N,T=f()
q=list(f())
print(T+sum(min(q[i+1]-q[i],T) for i in range(N-1)))

Buggy submission (verdict: Runtime Error):
N,W = map(int,input().split())

items = [tuple(map(int,input().split())) for i in range(N)]

from collections import defaultdict
dp = defaultdict(int) # w -> v
dp[0] = 0

for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w <= W:
      dp[tw+w] = max(tv+v, dp[tw+w])

print(max(dp.values()))