Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from heapq import heappush, heappop, heapify

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M = map(int,input().split())
A = sorted(map(int,input().split()))
acc = [0]+list(accumulate(A))

def judge(p):
    j = N
    cnt = 0
    for al in A:
        while j > 0 and al+A[j-1] >= p:
            j -= 1
        cnt += N-j
    return cnt <= M

p = bisect(0, A[-1]*2+1, judge)

j = N
cnt = 0
res = 0
q = []
for al in A:
    while j > 0 and al+A[j-1] >= p:
        j -= 1
    cnt += N-j
    res += (N-j)*al + acc[-1]-acc[j]
    if j > 0:
        q.append((-(al+A[j-1]),al,j-1))

heapify(q)
for _ in range(M-cnt):
    p,al,j = heappop(q)
    res -= p
    if j > 0:
        heappush(q, (-(al+A[j-1]),al,j-1))

print(res)

Fixed submission:
from itertools import accumulate

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M = map(int,input().split())
A = sorted(map(int,input().split()))
acc = [0]+list(accumulate(A))

def judge(p):
    j = N
    cnt = 0
    for al in A:
        while j > 0 and al+A[j-1] >= p:
            j -= 1
        cnt += N-j
    return cnt <= M

p = bisect(0, A[-1]*2+1, judge)

j = N
cnt = 0
res = 0
nv = 0
max2 = lambda x,y: x if x > y else y
for al in A:
    while j > 0 and al+A[j-1] >= p:
        j -= 1
    cnt += N-j
    res += (N-j)*al + acc[-1]-acc[j]
    if j > 0:
        nv = max2(nv, al+A[j-1])

res += nv*(M-cnt)
print(res)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M,V,P = map(int,input().split())
A = sorted(map(int,input().split()))
def judge(i):
    if len(A) <= P:
        return True
    a = A[i]
    if V <= P:
        return a+M >= A[-P]
    k = max2(0,V-P+1-i)
    if k-P >= 0:
        return False
    else:
        return a+M > A[-P+k]

i = bisect(-1,N-1,judge)
x = A[i]
while A[i-1] == x:
    i -= 1
print(N-i)


Fixed submission:
from bisect import bisect as list_bisect
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

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

k = N-P
def judge(i):
    if i >= k:
        return True
    a = A[i]
    if a+M < A[k]:
        return False

    r = 0
    for v in A[i+1:k+1]:
        r += a+M-v
    return r >= (V-P-i)*M

i = bisect(-1,N-1,judge)
print(N-i)
Buggy python submission (verdict: Runtime Error):
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

m,n = max((a,b) for a,b in zip(dist_u, dist_v) if a < b)
print(n-(m-n)%2)N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

m,n = max((a,b) for a,b in zip(dist_u, dist_v) if a < b)
print(n-(m-n)%2)

Fixed submission:
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

n = max(b for a,b in zip(dist_u, dist_v) if a < b)
m = min((b for a,b in zip(dist_u, dist_v) if a <= b), default=n)

print(max(n,m)-1)
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

X = int(input())

@lru_cache(None)
def rec(x):
    if x == 0:
        return True
    if x < 0:
        return False
    return any(rec(x-100-d) for d in range(6))

print(1 if rec(X) else 0)



Fixed submission:
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

X = int(input())

@lru_cache(None)
def rec(x):
    if x == 0:
        return True
    if x < 0:
        return False
    return any(rec(x-100-d) for d in range(6))

print(1 if rec(X) else 0)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = [float('inf')]*N
dp[-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = min(dp[i+1:min(N,i+M+1)])+1
if dp[0] == float('inf'):
    print(-1)
    exit()

dp += [float('inf')]*(M+1)
res = []
i = 0
while i < N-1:
    t = dp[i]
    s = min(k for k in range(1,M+1) if dp[i+k]==t-1)
    res.append(s)
    i += s
print(*res)

Fixed submission:

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

from operator import eq

N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = SegmentTree.all_identity(min, eq, float('inf'), N)
dp[N-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = dp[i+1:min(N,i+M+1)]+1
if dp[0] == float('inf'):
    print(-1)
    exit()

res = []
i = 0
while i < N-1:
    t = dp[i]
    k = 1
    while dp[i+k] != t-1:
        k += 1
    res.append(k)
    i += k
print(*res)
Buggy python submission (verdict: Runtime Error):

from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n, mod-2, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

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

d = X+Y

if d%3 != 0:
    print(0)
else:
    n = d//3

    res = comb(n,X-n, 10**9+7)[X-n]
    print(res)


Fixed submission:

from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n, mod-2, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

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

d = X+Y

if d%3 != 0:
    print(0)
else:
    n = d//3
    if X < n or 2*n < X:
        res = 0
    else:
        res = comb(n,X-n, 10**9+7)[X-n]
    print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
from bisect import bisect

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

def it():
    for i,j in combinations(range(N),2):
        if i+1 < j:
            a,c = L[i],L[j]

            yield max(0,j-bisect(L,abs(a-c), hi=j,lo=i+1))
print(sum(it()))

Fixed submission:
from itertools import combinations
from bisect import bisect

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

def it():
    for i,j in combinations(range(N),2):
        if i+1 < j:
            a,c = L[i],L[j]

            yield max(0,j-bisect(L,abs(a-c), hi=j,lo=i+1))
print(sum(it()))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import bellman_ford


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = bellman_ford(graph, directed=False)
    dist[dist<=L] = 1
    dist[dist>L] = 0

    dist = bellman_ford(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')

Fixed submission:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def solve(N,L,edges,queries):

    graph = np.zeros((N,N),dtype=int)
    for a,b,c in edges:
        graph[a-1,b-1] = c
        graph[b-1,a-1] = c

    dist = floyd_warshall(graph, directed=False)
    dist = (dist<=L)
    dist = floyd_warshall(dist, directed=False)
    res = []
    for a,b in queries:
        d = dist[a-1,b-1]
        res.append(int(d-1) if d != float('inf') else -1)
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':

    t = read().split()

    N,M,L = map(int,t[:3])

    m = map(int,t[3:M*3+3])
    edges = zip(m,m,m)

    Q = int(t[M*3+3])
    m = map(int, t[M*3+4:])
    queries = zip(m,m)

    print(*solve(N,L,edges,queries), sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

for l in reversed(range(1,N//2+1)):
    for i in range(N-2*l+1):
        for j in range(i+l,N-l+1):
            if S[i:i+l] == S[j:j+l]:
                print(l)
                exit()

print(0)

Fixed submission:
from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())
S = input()

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

for l in reversed(range(1,N//2+1)):
    for i in range(N-2*l+1):
        for j in range(i+l,N-l+1):
            print(S[i:i+l],S[j:j+l])
            if S[i:i+l] == S[j:j+l]:
                print(l)
                exit()

print(0)

Fixed submission:
from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())
S = input()

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)
Buggy python submission (verdict: Runtime Error):
S,T = input(),input()

print(sum(int(a==b) for a,b zip(S,T)))

Fixed submission:
S,T = input(),input()

print(sum(int(a==b) for a,b in zip(S,T)))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import count
N = int(input())

queues = [list(map(lambda x: int(x)-1,input().split()))[::-1] for _ in range(N)]

cnt = 0
goal = N*(N-1)//2
for day in count(1):
    used = [not bool(q) for q in queues]
    flag = False
    for i,u in enumerate(used):
        if not u:
            j = queues[i][-1]
            if not used[j] and queues[j][-1] == i:
                used[i] = True
                used[j] = True
                flag = True
                cnt += 1
                queues[i].pop()
                queues[j].pop()

    if cnt == goal:
        print(day)
        break
    elif not flag:
        print(-1)
        break

Fixed submission:

min2 = lambda x,y: x if x < y else y

N = int(input())

queues = [list(map(lambda x: int(x)-1,input().split()))[::-1] for _ in range(N)]

q = set()
for i,l in enumerate(queues):
    if i < l[-1] and queues[l[-1]][-1] == i:
        q.add(i)

d = 0
while q:
    possible = set()
    for v in q:
        u = queues[v].pop()
        queues[u].pop()
        possible.add(v)
        possible.add(u)

    q.clear()
    for v in possible:
        try:
            u = queues[v][-1]
            if queues[u][-1] == v:
                q.add(min2(u,v))
        except IndexError:
            pass
    d += 1

print(-1 if any(l for l in queues) else d)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)

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

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)

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

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

memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
stack = [(0,0)]
while stack:
    v,a = stack.pop()
    a += memo[v]
    result[v] = a
    for u in adj[v]:
        stack.append((u,a))

print(*result)

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

adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
def dfs(v,a):
    c = memo[v]
    for u in adj[v]:
        dfs(u,a+c)
    result[v] = a+c
dfs(0,0)
print(*result)

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

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

memo = [0]*N
for _ in range(Q):
    p,x = map(int,input().split())
    memo[p-1] += x

result = [None]*N
stack = [(0,0)]
while stack:
    v,a = stack.pop()
    a += memo[v]
    result[v] = a
    for u in adj[v]:
        stack.append((u,a))

print(*result)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
MOD = 10**9 + 7
memo = [0]*13
memo[0] = 1

c = 1
for d in reversed(s):
    if d == '?':
        nmemo = [0]*13
        for i in range(10):
            r = (i*c)%13
            for j in range(13):
                nmemo[(j+r)%13] += memo[j]
        for i in range(13):
            nmemo[i] %= MOD
        memo = nmemo
    else:
        d = (-int(d)*c)%13
        memo = memo[d:] + memo[:d]

    c *= 10
    c %= 13
print(memo[5])

Fixed submission:
s = input()
MOD = 10**9 + 7
memo = [0]*13
memo[0] = 1

c = 1
for d in reversed(s):
    if d == '?':
        nmemo = [0]*13
        for i in range(10):
            r = (i*c)%13
            for j in range(13):
                nmemo[(j+r)%13] += memo[j]
        for i in range(13):
            nmemo[i] %= MOD
        memo = nmemo
    else:
        d = (-int(d)*c)%13
        memo = memo[d:] + memo[:d]

    c *= 10
    c %= 13
print(memo[5])
Buggy python submission (verdict: Time Limit Exceeded):

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

adj = [list() for _ in range(N)]
for m in range(M):
    x,y,z = map(int,input().split())
    x,y = x-1,y-1
    adj[x].append(y)
    adj[y].append(x)

cnt = 0
unvisited = set(range(N))
while unvisited:
    u0 = next(iter(unvisited))
    unvisited.discard(u0)
    stack = [u0]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v in unvisited:
                unvisited.discard(v)
                stack.append(v)
    cnt += 1

print(cnt)

Fixed submission:
import scipy.sparse as sp
import scipy.sparse.csgraph as gp


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

adj = sp.dok_matrix((N,N), dtype=bool)
def it():
    for m in range(M):
        x,y,z = map(int,input().split())
        x,y = x-1,y-1
        adj[x,y] = True
        adj[y,x] = True
it()

res,_ = gp.connected_components(adj, directed=False)
print(res)
Buggy python 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()

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 python 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])


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 python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
H = list(map(int,input().split()))

dp = [0]*N
for i in range(1,N):
    dp[i] = min(abs(H[i]-H[i-n]) + dp[i-n] for n in range(1,min(K+1,i+1)))

print(dp[-1])

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 python 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])

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 python submission (verdict: Time Limit Exceeded):
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])


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 python submission (verdict: Time Limit Exceeded):
S,T = input(),input()

dp = [[0]*(len(T)+1) for _ in range(len(S)+1)]

for i in range(1,len(S)+1):
  for j in range(1,len(T)+1):
    dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

print(''.join(reversed(res)))

Fixed submission:
S,T = input(),input()

dp = [[0]*(len(T)+1) for _ in range(len(S)+1)]

for i in range(1,len(S)+1):
  for j in range(1,len(T)+1):
    dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

print(''.join(reversed(res)))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

def adj(v):
    t = 1
    while t <= 2*10**9:
        if t > v:
            yield t-v
        t *= 2

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1

degree = defaultdict(int)
for v in cnt.keys():
    for u in adj(v):
        if u == v:
            degree[v] += int(cnt.get(u,0) >= 2)
        else:
            degree[v] += int(cnt.get(u,0) >= 1)

stack = [v for v,c in degree.items() if c == 1]
res = 0
while stack:
    v = stack.pop()
    c = cnt.get(v,0)
    if c == 0:
        continue
    for u in adj(v):
        if u == v and cnt.get(u,0) >= 2:
            break
        elif cnt.get(u,0) >= 1:
            break
    res += 1
    del cnt[u]
    degree[u] -= 1
    if degree[u] == 1:
        stack.append(u)

print(res)

Fixed submission:
from collections import defaultdict

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

cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
res = 0
for x in reversed(A):
    y = (1 << x.bit_length()) - x
    if x == y:
        k = cnt[x]//2
    else:
        k = min(cnt[x], cnt[y])
    res += k
    cnt[x] -= k
    cnt[y] -= k

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

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