Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    to[u].append(v)
    to[v].append(u)

ans = [1 for _ in range(N)]

def dfs(u, p, L, length):
    print(u)
    ans[u] = length
    for v in to[u]:
        if v == p:
            continue
        L_copy = copy.deepcopy(L)
        if L[-1] < a[v]:
            L_copy.append(a[v])
            dfs(v, u, L_copy, length+1)
        else:
            p = bisect.bisect_left(L_copy, a[v])
            L_copy[p] = a[v]
            dfs(v, u, L_copy, length)

dfs(0, -1, [a[0]], 1)
for i in range(N):
    print(ans[i])


Fixed submission:
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

INF = 10**12
MAX_N = 202020

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    to[u].append(v)
    to[v].append(u)

dp = [INF for _ in range(MAX_N)]
ans = [0 for _ in range(N)]

def dfs(v, p=-1):
    i = bisect.bisect_left(dp, a[v])
    old = dp[i]
    dp[i] = a[v]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

dp[0] = -INF
dfs(0)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

infants = [[i, A[i]] for i in range(N)]
infants.sort(key=lambda x:x[1], reverse=True)

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

for x in range(N):
    for y in range(N-x):
        pos, infant = infants[x+y]
        dp[x][y+1] = max(dp[x][y+1], dp[x][y]+infant*abs(N-1-y-pos))
        dp[x+1][y] = max(dp[x+1][y], dp[x][y]+infant*abs(pos-x))

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

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

infants = [[i, A[i]] for i in range(N)]
infants.sort(key=lambda x:x[1], reverse=True)

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

for x in range(N):
    for y in range(N-x):
        pos, infant = infants[x+y]
        dp[x][y+1] = max(dp[x][y+1], dp[x][y]+infant*abs(N-1-y-pos))
        dp[x+1][y] = max(dp[x+1][y], dp[x][y]+infant*abs(pos-x))

ans = 0
for i in range(N):
    ans = max(ans, dp[i][N-i])
print(ans)
Buggy python submission (verdict: Runtime Error):
S=input()
ans="Yes"
if len(S)%2==1:
    ans="No"
else:
for i in range(len(S)):
    if i%2==0:
        if S[i]!="h":
            ans="No"
            break
    if i%2==1:
        if S[i]!="i":
            ans="No"
            break
print(ans)

Fixed submission:
S=input()
ans="Yes"
if len(S)%2==1:
    ans="No"
else:
    for i in range(len(S)):
        if i%2==0:
            if S[i]!="h":
                ans="No"
                break
        if i%2==1:
            if S[i]!="i":
                ans="No"
                break
print(ans)

Buggy python submission (verdict: Runtime Error):
S=input()
ans="Yes"
if S%2==1:
    ans="No"
else:
    for i in range(len(S)):
        if i%2==0:
            if S[i]!="h":
                ans="No"
                break
        if i%2==1:
            if S[i]!="i":
                ans="No"
                break
print(ans)

Fixed submission:
S=input()
ans="Yes"
if len(S)%2==1:
    ans="No"
else:
    for i in range(len(S)):
        if i%2==0:
            if S[i]!="h":
                ans="No"
                break
        if i%2==1:
            if S[i]!="i":
                ans="No"
                break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
Q=int(input())
query=[input().split() for _ in range(Q)]

reverse=False
for q in query:
    if q[0]=="1":
        reverse = not reverse
    else:
        if q[1]=="1":
            if reverse:
                S=S+q[2]
            else:
                S=q[2]+S
        else:
            if reverse:
                S=q[2]+S
            else:
                S=S+q[2]
if reverse:
    print(S[::-1])
else:
    print(S)

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

reverse=False
lst=["" for _ in range(500000+10)]
sp=200000+5
fp=200000+5

for i in range(len(S)):
    lst[sp+i]=S[i]
    fp+=1

for q in query:
    if q[0]=="1":
        reverse = not reverse
    else:
        if q[1]=="1":
            if reverse:
                #S=S+q[2]
                lst[fp]=q[2]
                fp+=1
            else:
                #S=q[2]+S
                sp-=1
                lst[sp]=q[2]
        else:
            if reverse:
                #S=q[2]+S
                sp-=1
                lst[sp]=q[2]
            else:
                #S=S+q[2]
                lst[fp]=q[2]
                fp+=1

if reverse:
    #print(S[::-1])
    print("".join(lst[::-1]))
else:
    #print(S)
    print("".join(lst))
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
S=input()
#dp=[[[0 for _ in range(P)] for _ in range(2)] for _ in range(N)]
dp=[[0 for _ in range(P)] for _ in range(N)]
#dp[0][1][int(S[0])%P]=1
dp[0][int(S[0])%P]=1

tmp=10%P

#print(dp)
for i in range(N-1):
    c=int(S[i+1])
    #print(c)
    for j in range(P):
        #dp[i+1][0][j]=dp[i][0][j]+dp[i][1][j]
        #dp[i+1][1][(tmp*j+c)%P]+=dp[i][1][j]
        dp[i+1][(tmp*j+c)%P]+=dp[i][j]
    #dp[i+1][1][c%P]+=1
    dp[i+1][c%P]+=1
    #print(dp)
#print(dp[N-1][0][0]+dp[N-1][1][0])
ans=0
for i in range(N):
    ans+=dp[i][0]
print(ans)

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

ans=0
if 10%P==0:
    for r in range(N):
        if int(S[r])%P==0:
            ans+=r+1
else:
    d=[0 for _ in range(N+1)] # Pで割った余りの累積和
    ten=1 # 10の何乗か
    for i in range(N-1, -1, -1): # 右から見ていく
        a=int(S[i])*ten%P
        d[i]=(d[i+1]+a)%P
        ten=(ten*10)%P
    cnt=[0 for _ in range(P)]
    for i in range(N, -1, -1):
        ans+=cnt[d[i]]
        cnt[d[i]]+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
S=input()
dp=[[[0 for _ in range(P)] for _ in range(2)] for _ in range(N)]

dp[0][1][int(S[0])%P]=1
tmp=10%P

#print(dp)
for i in range(N-1):
    c=int(S[i+1])
    #print(c)
    for j in range(P):
        dp[i+1][0][j]=dp[i][0][j]+dp[i][1][j]
        dp[i+1][1][(tmp*j+c)%P]+=dp[i][1][j]
    dp[i+1][1][c%P]+=1
    #print(dp)
print(dp[N-1][0][0]+dp[N-1][1][0])

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

ans=0
if 10%P==0:
    for r in range(N):
        if int(S[r])%P==0:
            ans+=r+1
else:
    d=[0 for _ in range(N+1)] # Pで割った余りの累積和
    ten=1 # 10の何乗か
    for i in range(N-1, -1, -1): # 右から見ていく
        a=int(S[i])*ten%P
        d[i]=(d[i+1]+a)%P
        ten=(ten*10)%P
    cnt=[0 for _ in range(P)]
    for i in range(N, -1, -1):
        ans+=cnt[d[i]]
        cnt[d[i]]+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M =map(int, input().split())
sc=[list(map(int, input().split())) for _ in range(M)]
sc.sort(key=lambda x:x[0])

ans=0
if M>N:
    ans=-1
for i in range(M):
    s1, c1 = sc[i]
    if s1>N:
        ans=-1
        break
    for j in range(i+1, M):
        s2, c2 = sc[j]
        if s1==s2 and c1!=c2:
            ans=-1
            break
if len(sc)!=1 and sc[0][0]==1 and sc[0][1]==0:
    ans=-1

if ans!=-1:
    ans_={1:1, 2:0, 3:0}
    for i in range(M):
        s, c = sc[i]
        ans_[s]=c
    for i in range(1, N+1):
        ans=ans*10+ans_[i]

print(ans)

Fixed submission:
N, M =map(int, input().split())
sc=[list(map(int, input().split())) for _ in range(M)]
sc.sort(key=lambda x:x[0])

ans=0
for i in range(M):
    s1, c1 = sc[i]
    if s1>N:
        ans=-1
        break
    for j in range(i+1, M):
        s2, c2 = sc[j]
        if s1==s2 and c1!=c2:
            ans=-1
            break
if M>0 and N>1 and sc[0][0]==1 and sc[0][1]==0:
    ans=-1

if ans!=-1:
    ans_={1:1, 2:0, 3:0}
    for i in range(M):
        s, c = sc[i]
        ans_[s]=c
    for i in range(1, N+1):
        ans=ans*10+ans_[i]

if N==1 and M==0:
    ans=0

print(ans)

Buggy python submission (verdict: Runtime Error):
N, M =map(int, input().split())
sc=[list(map(int, input().split())) for _ in range(M)]
sc.sort(key=lambda x:x[0])

ans=0
for i in range(M):
    s1, c1 = sc[i]
    if s1>N:
        ans=-1
        break
    for j in range(i+1, M):
        s2, c2 = sc[j]
        if s1==s2 and c1!=c2:
            ans=-1
            break
if sc[0][0]==1 and sc[0][1]==0:
    ans=-1

if ans!=-1:
    ans_={1:1, 2:0, 3:0, 4:0, 5:0}
    for i in range(M):
        s, c = sc[i]
        ans_[s]=c
    for i in range(1, N+1):
        ans=ans*10+ans_[i]

print(ans)

Fixed submission:
N, M =map(int, input().split())
sc=[list(map(int, input().split())) for _ in range(M)]
sc.sort(key=lambda x:x[0])

ans=0
for i in range(M):
    s1, c1 = sc[i]
    if s1>N:
        ans=-1
        break
    for j in range(i+1, M):
        s2, c2 = sc[j]
        if s1==s2 and c1!=c2:
            ans=-1
            break
if M>0 and N>1 and sc[0][0]==1 and sc[0][1]==0:
    ans=-1

if ans!=-1:
    ans_={1:1, 2:0, 3:0}
    for i in range(M):
        s, c = sc[i]
        ans_[s]=c
    for i in range(1, N+1):
        ans=ans*10+ans_[i]

if N==1 and M==0:
    ans=0

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000+10)

N, M, K=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(M)]
CD=[list(map(int, input().split())) for _ in range(K)]
if M==0:
    print("haha")
else:
    AB.sort(key=lambda x:(x[0], x[1]))
    if K!=0:
        CD.sort(key=lambda x:(x[0], x[1]))

    fr=[[] for _ in range(N)] # friends relation
    br=[[] for _ in range(N)] # block relation

    AB.sort(key=lambda x:(x[0], x[1]))
    CD.sort(key=lambda x:(x[0], x[1]))
    for A, B in AB:
        A-=1
        B-=1
        fr[A].append(B)
        fr[B].append(A)
    for C, D in CD:
        C-=1
        D-=1
        br[C].append(D)
        br[D].append(C)

    counts=[0 for _ in range(N)]
    visited=[False for _ in range(N)]

    def dfs(u, p=-1, nodes=[]):
        visited[u]=True
        for n in nodes:
            if n not in fr[u] and n not in br[u]:
                counts[u]+=1
                counts[n]+=1
        nodes.append(u)
        for v in fr[u]:
            if v==p:
                continue
            if visited[v]:
                continue
            dfs(v, p=u, nodes=nodes)

    for i in range(N):
        if not visited[i]:
            dfs(i, p=-1, nodes=[])

print(*counts)


Fixed submission:
# 小さい方の木を大きい方にくっつける O(logN)
# 経路縮約(メモ化) ならしO(logN)
# 両方やると、ならしO(α(N)) α: カルマン関数

# 実装
# 子: 親のID, 根: -サイズ (非負: 子, 負: 根)
# atcoder ABC 158 解説に詳細
class UnionFind():

    def __init__(self, n=0):
        self.d = [-1 for _ in range(N)] # 経路縮約のためのメモ
    
    def find(self, x): # xが所属するグループの親を返す
        if self.d[x]<0:
            return x
        res = self.find(self.d[x])
        self.d[x] = res # 経路縮約の箇所
        return res
    
    def unite(self, x, y): # x, yが所属するグループを結合する, 結合に成功したらTrue, すでに結合していたらFalse
        # まずx, yをそれぞれの親にする
        x = self.find(x)
        y = self.find(y) 
        if x==y:
            return False
        # xの方が大きい木になるようにする (サイズは負であることに注意)
        if self.d[x] > self.d[y]: 
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y): # 同じ集合に属しているかどうかを判定する
        return self.find(x) == self.find(y)
    
    def size(self, x): # xが所属しているグループのサイズを返す
        return -self.d[self.find(x)]

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

uf = UnionFind(N)
deg = [0 for _ in range(N)] # 友達関係にある人の個数(グラフにおける各頂点の次数)を保持
to = [[] for _ in range(N)] # ブロック関係にある人に枝を張る

# 友達関係
for i in range(M):
    a, b = AB[i]
    a-=1
    b-=1
    deg[a]+=1
    deg[b]+=1
    uf.unite(a, b)
# ブロック関係
for i in range(K):
    c, d = CD[i]
    c-=1
    d-=1
    to[c].append(d)
    to[d].append(c)
# 答え
ans=[0 for _ in range(N)]
for i in range(N):
    # 各人(頂点)の所属するグループのサイズから、自分自身と、直接の友達関係を引く
    ans[i]=uf.size(i)-1-deg[i]
    # 各人のブロック関係にある人が同じグループに所属している場合は、答えを-する
    for u in to[i]:
        if uf.same(i, u):
            ans[i]-=1
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

INF = 10**9
dp = [[INF for _ in range(H+10)] for _ in range(N+1)]

for i in range(1, N+1):
    a, b = magic[i-1]
    dp[i][0] = 0
    for j in range(1, H+1):
        dp[i][j] = min(dp[i][max(0, j-a)]+b, dp[i-1][j])

print(dp[N][H])

Fixed submission:
H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])
dp=[[0 for _ in range(H+1)] for _ in range(N)]
A, B=AB[0]
for j in range(1, H+1):
  dp[0][j]=((j-1)//A+1)*B
for i in range(1, N):
  A, B=AB[i]
  for j in range(H+1):
    if j>=A:
      dp[i][j]=min(dp[i-1][j], dp[i-1][j-A]+B, dp[i][j-A]+B)
    else:
      dp[i][j]=min(dp[i-1][j], B)
print(dp[N-1][H])
Buggy python submission (verdict: Time Limit Exceeded):
N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[pos]-1)//A+1
  start, end=pos, bomb_j[pos]+1
  for i in range(start, end):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
print(ans)

Fixed submission:
from collections import deque

N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
total=0
q=deque()
ans=0

for i in range(N):
  X, H=XH[i]
  while len(q) and q[0][0]<X:
    total-=q.popleft()[1]
  H-=total
  if H>0:
    attack_cnt=(H-1)//A+1
    ans+=attack_cnt
    damage=attack_cnt*A
    total+=damage
    q.append([X+2*D, damage])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[i]-1)//A+1
  for i in range(pos, bomb_j[pos]+1):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
print(ans)

Fixed submission:
from collections import deque

N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
total=0
q=deque()
ans=0

for i in range(N):
  X, H=XH[i]
  while len(q) and q[0][0]<X:
    total-=q.popleft()[1]
  H-=total
  if H>0:
    attack_cnt=(H-1)//A+1
    ans+=attack_cnt
    damage=attack_cnt*A
    total+=damage
    q.append([X+2*D, damage])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
bomb_j=[0 for _ in range(N)]

for i in range(N):
  X=XH[i][0]
  left, right=0, N-1
  while left<=right:
    mid=(left+right)//2
    if XH[mid][0]>X+2*D:
      right=mid-1
    else:
      left=mid+1
  bomb_j[i]=left-1

ans, pos=0, 0
Hs=[H for X, H in XH]
while pos<N:
  attack=(Hs[i]-1)//A+1
  for i in range(pos, bomb_j[pos]+1):
    Hs[i]=max(0, Hs[i]-attack*A)
  while pos<N and Hs[pos]==0:
    pos+=1
  ans+=attack
print(ans)

Fixed submission:
from collections import deque

N, D, A=map(int, input().split())
XH=[list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x:x[0])
total=0
q=deque()
ans=0

for i in range(N):
  X, H=XH[i]
  while len(q) and q[0][0]<X:
    total-=q.popleft()[1]
  H-=total
  if H>0:
    attack_cnt=(H-1)//A+1
    ans+=attack_cnt
    damage=attack_cnt*A
    total+=damage
    q.append([X+2*D, damage])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
from functools import reduce

MOD=10**9+7

def lcm_base(x, y):
  return (x*y)//gcd(x,y)

N=int(input())
A=list(map(int, input().split()))
lcm=reduce(lcm_base, A, 1)
ans=0
for i in range(N):
  ans+=lcm//A[i]
print(ans%MOD)

Fixed submission:
from fractions import gcd
from functools import reduce

MOD=10**9+7

def lcm_base(x, y):
  return (x*y)//gcd(x,y)

N=int(input())
A=list(map(int, input().split()))
ans=1
lcm=A[0]
for i in range(1, N):
  prelcm=lcm
  lcm=lcm_base(prelcm, A[i])
  ans=ans*(lcm//prelcm)+lcm//A[i]
print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
lst=[input().split() for _ in range(M)]
AC=[False for _ in range(N)]
WA=[0 for _ in range(N)]
for p, S in lst:
  p=int(p)-1
  if S=="AC":
    AC[p]=True
  if S=="WA" and not AC[p]:
    WA[p]+=1
for i in range(M):
  if not AC[p]:
    WA[i]=0
print(sum(AC), sum(WA))

Fixed submission:
N, M=map(int, input().split())
lst=[input().split() for _ in range(M)]
AC=[False for _ in range(N)]
WA=[0 for _ in range(N)]
for p, S in lst:
  p=int(p)-1
  if S=="AC":
    AC[p]=True
  if S=="WA" and not AC[p]:
    WA[p]+=1
for i in range(N):
  if not AC[i]:
    WA[i]=0
print(sum(AC), sum(WA))

Buggy python submission (verdict: Runtime Error):
N, M=map(int, input().split())
lst=[input().split() for _ in range(M)]
AC=[False for _ in range(N)]
WA=[0 for _ in range(N)]
for p, S in lst:
  p=int(p)-1
  if S=="AC":
    AC[p]=True
  if S=="WA" and not AC[p]:
    WA[p]+=1
for i in range(N):
  if not AC[p]:
    WA[i]=0
print(sum(AC), sum(WA))

Fixed submission:
N, M=map(int, input().split())
lst=[input().split() for _ in range(M)]
AC=[False for _ in range(N)]
WA=[0 for _ in range(N)]
for p, S in lst:
  p=int(p)-1
  if S=="AC":
    AC[p]=True
  if S=="WA" and not AC[p]:
    WA[p]+=1
for i in range(N):
  if not AC[i]:
    WA[i]=0
print(sum(AC), sum(WA))
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
 
def framod(n, mod, a=1):
  for i in range(1,n+1):
    a=a * i % mod
  return a
  
def power(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return power(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
  a=framod(n, mod)
  b=framod(k, mod)
  c=framod(n-k, mod)
  return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

N, K=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
ans=0
for i in range(N-K+1):
  n, r=N-i-1, K-1
  ans=(ans+(A[-(i+1)]-A[i])*comb(n, r, mod)%mod)%mod
print(ans)


Fixed submission:
def comb(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**5+10
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 )

N, K=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
ans=0
for i in range(N-K+1):
  n, r=N-i-1, K-1
  ans=(ans+(A[-(i+1)]-A[i])*comb(n, r, mod)%mod)%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)

Fixed submission:
MOD=10**9+7
MAXN=4*(10**5)

two_power=[1 for _ in range(MAXN+10)]
for i in range(1, MAXN+10):
    two_power[i]=(two_power[i-1]*2)%MOD

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=two_power[2*n-1]
d=two_power[2*n-2]
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans=(ans+(x+i*d)*c[i])%MOD
print(ans)

Fixed submission:
MOD=10**9+7
MAXN=4*(10**5)

two_power=[1 for _ in range(MAXN+10)]
for i in range(1, MAXN+10):
    two_power[i]=(two_power[i-1]*2)%MOD

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=two_power[2*n-1]
d=two_power[2*n-2]
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
H, W=map(int, input().split())
maxK=80*80+1
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
dp=[[[0 for _ in range(maxK+1)] for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][C[0][0]]=1
for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(maxK):
            if dp[i-1][j][k]==1 or dp[i][j-1][k]==1:
                k_candidate1, k_candidate2=abs(k-C[i-1][j-1]), abs(k+C[i-1][j-1])
                if k_candidate1<maxK:
                    dp[i][j][k_candidate1]=1
                if k_candidate2<maxK:
                    dp[i][j][k_candidate2]=1
for k in range(maxK):
    if dp[H][W][k]==1:
        print(k)
        break

Fixed submission:
A=list(map(int, input().split()))
if sum(A)>=22:
    print('bust')
else:
    print('win')
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)

Fixed submission:
N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W=map(int, input().split())
maxK=80*80+1
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
dp=[[[0 for _ in range(maxK+1)] for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][C[0][0]]=1
for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(maxK):
            if dp[i-1][j][k]==1 or dp[i][j-1][k]==1:
                k_candidate1, k_candidate2=abs(k-C[i-1][j-1]), abs(k+C[i-1][j-1])
                if k_candidate1<maxK:
                    dp[i][j][k_candidate1]=1
                if k_candidate2<maxK:
                    dp[i][j][k_candidate2]=1
for k in range(maxK):
    if dp[H][W][k]==1:
        print(k)
        break

Fixed submission:
H, W=map(int, input().split())
maxK=80*80+1
A=[list(map(int, input().split())) for _ in range(H)]
B=[list(map(int, input().split())) for _ in range(H)]
C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
dp=[[[0 for _ in range(maxK+1)] for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][C[0][0]]=1
for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(maxK):
            if dp[i-1][j][k]==1 or dp[i][j-1][k]==1:
                k_candidate1, k_candidate2=abs(k-C[i-1][j-1]), abs(k+C[i-1][j-1])
                if k_candidate1<maxK:
                    dp[i][j][k_candidate1]=1
                if k_candidate2<maxK:
                    dp[i][j][k_candidate2]=1
for k in range(maxK):
    if dp[H][W][k]==1:
        print(k)
        break