Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = input()
N = int(N)
W = [int(i) for i in input().split()]

Total = sum(W)
for i in range(len(W)):
  sub_Total = sum(W[:i])
  if Total/2 < sub_Total:
    diff1 = abs(Total - 2*sub_Total)
    diff2 = abs(Total - 2*sum(W[:i-1]))
    break
    
print(min(diff1, diff2))

Fixed submission:
N = input()
N = int(N)
W = [int(i) for i in input().split()]

Total = sum(W)
sub_Total = 0
for i in range(len(W)):
  pre_sub_Total = sub_Total
  sub_Total = sub_Total + W[i]
  if Total/2 < sub_Total:
    diff1 = abs(Total - 2*sub_Total)
    diff2 = abs(Total - 2*pre_sub_Total)
    break

print(min(diff1, diff2))
Buggy python submission (verdict: Runtime Error):
list_SP = []
N = int(input())

for i in range(N):
  S, P = input().split()
  list_SP.append([S, 100 - int(P), i+1])
  
  
sorted_listSP = sorted(list_SP)
print(sorted_listSP[2])

Fixed submission:
list_SP = []
N = int(input())

for i in range(N):
  S, P = input().split()
  list_SP.append([S, 100 - int(P), i+1])
  
  
sorted_listSP = sorted(list_SP)
for data in sorted_listSP:
  print(data[2])
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
n = int(input())
A=[int(input()) for _ in range(n)]
row = [A[0]]
for a in A[1:]:
    if a<=row[-1]:
        row.append(a)
    else:
        row[len(row) - bisect_left(row[::-1],a)] = a
print(len(row))

Fixed submission:
r = int(input())
print(3*(r**2))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int,input().split()))
for x in range(A[0]+1):
    t = x
    B = [x]
    for i in range(n-1):
        B.append(A[i]-t)
        t = B[-1]
    if 2*sum(B)==sum(A):
        break
ans = [i*2 for i in B]
print(" ".join(map(str,ans)))

Fixed submission:
n = int(input())
A = list(map(int,input().split()))
x = 0
for i in range(n):
    if i%2==0:
        x+=A[i]
    else:
        x-=A[i]
B = [x//2]
for i in range(n-1):
    B.append(A[i]-B[-1])
ans = [2*b for b in B]
print(" ".join(map(str,ans)))
Buggy python submission (verdict: Runtime Error):
n, k = map(int,input().split())
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**9)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in range(k):
    ans = 0
    ans += cmb(n-k+1,i+1)*cmb(k-1,i)
    ans %= MOD
    print(ans)

Fixed submission:
n, k = map(int,input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(k):
    print(cmb(n-k+1,i+1,mod)*cmb(k-1,i,mod)%mod)

Buggy python submission (verdict: Runtime Error):
n, k = map(int,input().split())
MOD = 10**9 + 7

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(k):
    ans = 0
    ans += cmb(n-k+1,i+1)*cmb(k-1,i)
    ans %= MOD
    print(ans)

Fixed submission:
n, k = map(int,input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(k):
    print(cmb(n-k+1,i+1,mod)*cmb(k-1,i,mod)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import takewhile

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

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Fixed submission:
from itertools import takewhile

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

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
S = [input() for _ in range(H)]

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Fixed submission:
from itertools import takewhile

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

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
card = [0]*n
for i in range(m):
    l,r = map(int,input().split())
    l -= 1
    card[l:r] = list(map(lambda x:x+1, card[l:r]))
print(card.count(m))

Fixed submission:
n,m = map(int,input().split())
card = [0]*n
l,r = 1,n
for i in range(m):
    tmp_l,tmp_r = map(int,input().split())
    if l < tmp_l:
        l=tmp_l
    if r > tmp_r:
        r = tmp_r
ans = 0
if r-l>=0:
    ans = r-l+1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect

n,m = map(int,input().split())
an = list(map(int,input().split()))

for i in range(m):
    an.sort()
    b,c=map(int,input().split())
    cnt = bisect(an,c)
    if b <= cnt:
        for j in range(b):
            an[j]=c
    else:
        for j in range(cnt):
            an[j]=c
print(sum(an))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
for i in range(M):
    b, c = map(int, input().split())
    D.append((b, c))
A = sorted(A)
D = sorted(D, key=lambda x: x[1], reverse=True)

i = 0
for j in range(M):
    p, q = D[j]
    while p > 0:
        if i < N and q > A[i]:
            A[i] = q
            i += 1
        else:
            break
        p -= 1
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
an = list(map(int,input().split()))

for i in range(m):
    b,c=map(int,input().split())
    for j in range(b):
        tmp_min = min(an)
        if c > tmp_min:
            an[an.index(tmp_min)] = c
print(sum(an))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
for i in range(M):
    b, c = map(int, input().split())
    D.append((b, c))
A = sorted(A)
D = sorted(D, key=lambda x: x[1], reverse=True)

i = 0
for j in range(M):
    p, q = D[j]
    while p > 0:
        if i < N and q > A[i]:
            A[i] = q
            i += 1
        else:
            break
        p -= 1
print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H,W = map(int,input().split())
src = [input() for _ in range(H)]

dxy = [(0,1),(1,0),(0,-1),(-1,0)]

dist = [[-1]*W for _ in range(H)]
d = deque([])

for h in range(H):
    for w in range(W):
        if src[h][w]=="#":
            dist[h][w]=0
            d.append((w,h))
while d:
    x,y = d.popleft()
    for dx, dy in dxy:
        nx,ny = x+dx, y+dy
        if not 0<=nx<W: continue
        if not 0<=ny<H: continue
        if src[ny][nx] == "#": continue
        if dist[ny][nx] > 0: continue
        dist[ny][nx] = dist[y][x] + 1
        d.append((nx,ny))
print(max(map(max,dist)))

Fixed submission:
from collections import deque

H,W = map(int,input().split())
src = [input() for _ in range(H)]

dxy = [(0,1),(1,0),(0,-1),(-1,0)]

dist = [[-1]*W for _ in range(H)]
d = deque([])

for h in range(H):
    for w in range(W):
        if src[h][w]=="#":
            dist[h][w]=0
            d.append((w,h))
while d:
    x,y = d.popleft()
    for dx, dy in dxy:
        nx,ny = x+dx, y+dy
        if not 0<=nx<W: continue
        if not 0<=ny<H: continue
        if src[ny][nx] == "#": continue
        if dist[ny][nx] > 0: continue
        dist[ny][nx] = dist[y][x] + 1
        d.append((nx,ny))
print(max(map(max,dist)))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

X = [0]*N
Y = [0]*N

for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])

Z = [0]*n
for i in range(N):
    Z[i]=gcd(X[i],Y[i])
print(max(Z))

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

X = [0]*N
Y = [0]*N

for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])

Z = [0]*N
for i in range(N):
    Z[i]=gcd(X[i],Y[i])
print(max(Z))
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S=input()
for _ in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    s = S[l-1:r]
    for i in range(len(s)-1):
        if s[i]=="A" and s[i+1]=="C":
            cnt += 1
    print(cnt)

Fixed submission:
N,Q = map(int,input().split())
S=input()
ans_l = [0]*N
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        ans_l[i+1] = ans_l[i] + 1
    else:
        ans_l[i+1] = ans_l[i]
for _ in range(Q):
    l, r = map(int, input().split())
    ans = ans_l[r-1] - ans_l[l-1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
tmp = N*(N-1)//2
l = []
cnt = []
ab = [list(map(int, input().split())) for i in range(M)]
# print(ans)
herasu = 0
ans = [tmp]
for i in ab[::-1]:
    
    if (i[0] in cnt) and (i[1] in cnt):
#         print("両方ある")
        for index, l1 in enumerate(l):
            if i[0] in l1:
                tmp0 = index
            if i[1] in l1:
                tmp1 = index
        herasu += len(l[tmp0])*len(l[tmp1])
        del(l[tmp0])
        del(l[tmp1])
        l.append(l[tmp0]+l[tmp1])
        
        
    if (i[0] not in cnt) and (i[1] not in cnt):
#         print("両方ない")
        cnt += [i[0],i[1]]
        l.append(i)
        herasu += 1
        
    else:
#         print("片方しか入ってない")
        for l1 in l:
#             print(l1)
            if i[0] in l1:
#                 print(i[0], "がl1にあった")
                herasu += len(l1)
                l1.append(i[1])
                break
            if i[1] in l1:
                
                herasu += len(l1)
                l1.append(i[0])
                break
    
    ans.append(tmp-herasu)
    
for i in ans[::-1][1:]:
    print(i)


Fixed submission:
class UnionFind:
    def __init__(self,size):
        self.par = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]
        
    # xの根を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
            
    # xとyを同じグループに
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
        else:
            self.par[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        
    # xとyが同じグループか判定
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
N,M = map(int,input().split())
s = N*(N-1)//2
ans = []
ab = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

tree = UnionFind(N)

for index, bridge in enumerate(ab[::-1]):
    if tree.same(bridge[0],bridge[1]):
        ans.append(s)
    else:
        d = tree.size[tree.find(bridge[0])] * tree.size[tree.find(bridge[1])]
        tree.union(bridge[0],bridge[1])
        ans.append(s)
        s -= d
        
print("\n".join(map(str, ans[::-1])))
Buggy python submission (verdict: Runtime Error):
N,A,B,C = map(int, input().split())
l = [int(i) for i in input()]
INF = 10**9
def dfs(cur,a,b,c):
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0 else INF
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+l[cur],b,c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))

Fixed submission:
N,A,B,C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10**9
def dfs(cur,a,b,c):
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C) - 30 if min(a,b,c) > 0 else INF
    ret0 = dfs(cur+1,a,b,c)
    ret1 = dfs(cur+1,a+l[cur],b,c) + 10
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)
print(dfs(0,0,0,0))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

A,B,Q = map(int,input().split())
sa = [int(input()) for i in range(A)]
tb = [int(input()) for i in range(B)]
xq = [int(input()) for i in range(Q)]

for x in xq:
    ans = 0
    near_s = sa[np.argmin([abs(s-x) for s in sa])]
    near_t = tb[np.argmin([abs(near_s-t) for t in tb])]
    ans += abs(near_s-x)+abs(near_t-near_s)
    
    ans2 = 0
    near_t_2 = tb[np.argmin([abs(t-x) for t in tb])]
    near_s_2 = sa[np.argmin([abs(near_t_2-s) for s in sa])]
    ans2 += abs(near_t_2-x) + abs(near_s_2 -near_t_2)
    print(min(ans,ans2))

Fixed submission:
import bisect

A,B,Q = map(int,input().split())
INF = 10**18
sa = [-INF] + [int(input()) for i in range(A)] + [INF]
tb = [-INF] + [int(input()) for i in range(B)] + [INF]
xq = [int(input()) for i in range(Q)]

for x in xq:
    ans = INF
#     near_s = sa[np.argmin([abs(s-x) for s in sa])]
#     near_t = tb[np.argmin([abs(near_s-t) for t in tb])]
#     ans += abs(near_s-x)+abs(near_t-near_s)
    
#     ans2 = 0
#     near_t_2 = tb[np.argmin([abs(t-x) for t in tb])]
#     near_s_2 = sa[np.argmin([abs(near_t_2-s) for s in sa])]
#     ans2 += abs(near_t_2-x) + abs(near_s_2 -near_t_2)

    b, d = bisect.bisect_right(sa,x), bisect.bisect_right(tb,x)
    for S in [sa[b],sa[b-1]]:
        for T in [tb[d], tb[d-1]]:
            d1, d2 = abs(S-x) + abs(T-S), abs(T-x) + abs(T-S)
            ans = min(ans,d1,d2)
    
    print(ans)
Buggy python submission (verdict: Runtime Error):
from fraction import gcd
from functools import reduce

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

print(reduce(gcd, an))

Fixed submission:
from fractions import gcd
from functools import reduce

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

print(reduce(gcd, an))

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

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

print(reduce(math.gcd, an))

Fixed submission:
from fractions import gcd
from functools import reduce

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

print(reduce(gcd, an))
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[n])

Fixed submission:
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])

Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,n+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[n])

Fixed submission:
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])

Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,n+1):
    for x in a:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[n])

Fixed submission:
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])
Buggy python submission (verdict: Runtime Error):
from collections import Counter

s = int(input())
a = [s]
def f_even(n):
    return n//2
def f_odd(n):
    return 3*n + 1
for i in range(100):
    if a[i]%2 == 0:
        a.append(f_even(a[i]))
    else:
        a.append(f_odd(a[i]))
    tmp = Counter(a).most_common()[0]
    if tmp[1] > 1:
        print(i+2)
        return

Fixed submission:
s = int(input())
lst = []

while s not in lst:
    lst.append(s)
    s = s/2 if s%2==0 else 3*s + 1
    
print(len(lst) + 1)
Buggy python submission (verdict: Runtime Error):
n = input()
hn = list(map(int, input().split()))

ans = 0

while sum(hn) > 0:
    ans+= 1
    flag = False
    for i in range(n):
        if hn[i] > 0:
            hn[i] -= 1
            flag = True
        else:
            break

print(ans)

Fixed submission:
n = int(input())
hn = list(map(int, input().split()))

ans = 0

while sum(hn) > 0:
    ans+= 1
    flag = False
    for i in range(n):
        if hn[i] > 0:
            hn[i] -= 1
            flag = True
        elif flag is True:
            break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n,k = map(int,input().split())

td = []
for i in range(n):
    td_tmp = list(map(int,input().split()))
    td.append(td_tmp)

# 貪欲で

td_comb = list(itertools.combinations(td, k))

ans = 0

for i in td_comb:
    tmp_ans = 0
    cnt = 0
    t_lst = []
    for j in i:
        tmp_ans += j[1]
        if j[0] not in t_lst:
            cnt += 1
            t_lst.append(j[0])
    tmp_ans += cnt**2
    ans = tmp_ans if tmp_ans>ans else ans

print(ans)

Fixed submission:
N, K = map( int, input().split())
T = [(0,0)]*N
for i in range(N):
    t, d = map( int, input().split())
    T[i] = (d,t)
T.sort( key= None, reverse = True)
C = T[:K]
AC = T[K:]
kiso = 0
s = 0
S = [0]*(N+1)
for i in range(K):
    d, t = T[i]
    kiso += d
    if S[t] == 0:
        S[t] = 1
        s += 1
    else:
        S[t] += 1
ans = kiso + s**2
C.sort()
r = 0
 
for i in range(K):
    d, t = C[i]
    if S[t] >= 2:
        while r < N-K:
            if S[ AC[r][1]] == 0:
                S[t] -= 1
                S[ AC[r][1]] += 1
                s += 1
                kiso -= d
                kiso += AC[r][0]
                r += 1
                break
            r += 1
    ans = max( ans, kiso + s**2)
print( ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
hn = list(map(int,input().split()))
#初期値
inf=float("inf")
dp=[inf]*(N+2)
dp[0], dp[1] = 0, abs(hn[1]-hn[0])

# DP
for i in range(2,N):
    kouho = []
    for j in range(1,K+1): kouho.append(dp[i-j]+abs(hn[i]-hn[i-j]))
    dp[i] = min(kouho)
print(dp[N-1])

Fixed submission:
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):
    start = max(i-K,0)
    dp[i] = np.min(dp[start:i] + np.abs(H[i] - H[start:i]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = [[0]*(W+1) for _ 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],  wv[i-1][1] + dp[i-1][j - wv[i-1][0]])
        
print(dp[-1][-1])

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

dp = [[0]*(W+1) for _ 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],  wv[i-1][1] + dp[i-1][j - wv[i-1][0]])
        
print(dp[-1][-1])