Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
N,S=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=998244353
cur=defaultdict(lambda: 0)
new=defaultdict(lambda: 0)
cur[0]=1

for a in A:
    for i in cur.keys():
        new[i+a]+=cur[i]*1
        new[i+a]%=mod
        new[i]+=cur[i]*2
        new[i]%=mod
    cur=new
    new=defaultdict(lambda: 0)

print cur[S]


Fixed submission:
import sys
from collections import defaultdict
N,S=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=998244353
cur=defaultdict(lambda: 0)
new=defaultdict(lambda: 0)
cur[0]=1

for a in A:
    for i in cur.keys():
        if i+a<=S:
            new[i+a]+=cur[i]*1
            new[i+a]%=mod
        new[i]+=cur[i]*2
        new[i]%=mod
    cur=new
    new=defaultdict(lambda: 0)

print cur[S]
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N=input()

#約数列挙
def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n/i:
                divisors.append(n/i)
    return divisors

def func(a,b):
    return a**5-b**5

L=make_divisors(N)
for yakusu in L:
    for a in range(N):
        b=a-yakusu
        ret=func(a,b)
        if ret==N:
            print a,b
            quit()
        elif N<ret:
            continue


Fixed submission:
N=input()
for a in range(-200,200):
    for b in range(-200,200):
        if a**5-b**5==N:
            print a,b
            quit()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N=input()

#約数列挙
def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n/i:
                divisors.append(n/i)
    return divisors

def func(a,b):
    return a**5-b**5

L=make_divisors(N)

for yakusu in L:
    for a in range(N):
        b=a-yakusu
        ret=func(a,b)
        if ret==N:
            print a,b
            quit()


Fixed submission:
N=input()
for a in range(-200,200):
    for b in range(-200,200):
        if a**5-b**5==N:
            print a,b
            quit()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N=sys.stdin.readline().strip()
ans=0

length=len(N)

for r in range(1,length+1):
    for l in range(r):
        n=int(N[l:r])
        if n%2019==0:
            ans+=1
print ans 


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=sys.stdin.readline().strip()
N=N[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(N):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現回数に+1カウント
print ans
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x in L:
    if x in R[bisect_left(R,x):]:
        print x+1

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C


for x in L:
    if x in R:
        print x+1

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque

S=raw_input()
Q=input()
Query=[ sys.stdin.readline().split() for _ in range(Q) ]

s1=deque()
s2=deque()
judge={}
judge["front"]="s1"
judge["end"]="s2"

cnt=0
for x in Query:
    if x[0]=="1":
        n=x[0]
        cnt+=1
    elif x[0]=="2":
        n,f,c=x[0],x[1],x[2]
    if n=="1":
        judge["front"],judge["end"]=judge["end"],judge["front"]
    elif n=="2":
        if f=="1":
            if judge["front"]=="s1":
                s1.appendleft(c)
            elif judge["front"]=="s2":
                s2.appendleft(c)
        elif f=="2":
            if judge["end"]=="s1":
                s1.append(c)
            if judge["end"]=="s2":
                s2.append(c)

str1=""
for x in s1:
    str1+=x
str2=""
for x in s2:
    str2+=x

if cnt%2==0:
    print str1[::-1]+S+str2
elif cnt%2==1:
    print str2+S[::-1]+str1[::-1]


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

ans=0
if P in (2,5):
    len_S=len(S)
    for i,x in enumerate(S):
        x=int(x)
        if x%P==0:
            ans+=(len_S-i)
    print ans
else:
    L=[0] 
    val=0
    for i,x in enumerate(S):
        x=int(x)
        val+=pow(10,i,P)*x
        L.append(val%P)

    C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
    for x in L:
        ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
        C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
    print ans
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #（攻撃が無効となる座標、攻撃によるポイント）
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break  #無効となる攻撃がない場合はwhileを終了
        end_x,end_point=q.popleft()
        attack_point-=end_point 　#攻撃が無効となる座標<=現在の座標があれば、その攻撃のポイントを引く

    if h<=attack_point: #モンスターの体力よりも攻撃で減らせるポイントの方が大きければ新規攻撃は不要
        pass
    else:   #新規攻撃が必要な場合
        if h%A==0:
            cnt=(h-attack_point)/A  #モンスターの大量をゼロ以下にするために何回攻撃が必要か
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))   #（攻撃が無効となる座標、攻撃によるポイント）をキューに入れる
        ans+=cnt

print ans

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,D,A=map(int, sys.stdin.readline().split())
XH=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
XH.sort()

q=deque()   #攻撃が無効となる座標、攻撃から差し引くポイント
ans=0
cnt=0

attack_point=0
for x,h in XH:
    while q:
        if x<q[0][0]:break
        end_x,end_point=q.popleft()
        attack_point-=end_point

    if h<=attack_point:
        pass
    else:
        if h%A==0:
            cnt=(h-attack_point)/A
        else:
            cnt=(h-attack_point)/A+1
        attack_point+=cnt*A
        q.append((x+2*D+1,cnt*A))
        ans+=cnt

print ans
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

mod=10**9+7
def lcm(a, b):
    return a*b/gcd(a, b)

lc=1
for a in A:
    lc=lcm(lc,a)

ans=0
for a in A:
    b=lc/a
    ans+=b

print ans%mod

Fixed submission:
import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

mod=10**9+7
def lcm(a, b):
    g=gcd(a, b)
    return a*b/gcd(a, b)

lc=1
for a in A:
    lc=lcm(lc,a)

ans=0
for a in A:
    b=lc*pow(a,mod-2,mod)
    ans+=b

print ans%mod
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict

H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

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

def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: 0)    #距離

    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=L[(fro_x,fro_y)]+1
                    q.append((to_x,to_y))

    return max(L.values())

ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,bfs((h,w)))

print ans


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    L=defaultdict(lambda: float("inf")) 
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            alt=L[(fro_x,fro_y)]+1
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and alt<L[(to_x,to_y)]:
                    L[(to_x,to_y)]=alt
                    q.append((to_x,to_y))
    return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))
print ans
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)*pow(2,mod-2,mod)+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

ans=0
for c,d in zip(C,D):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod


Fixed submission:
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        next=(2*D[-1]-d0)*pow(2,mod-2,mod)+d0
        D.append(next%mod)

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、Dは配列を逆順にしたものを足し合わせる
#modを取っているので、Dを降順ソートすると順番が崩れる
ans=0
for c,d in zip(C,D[::-1]):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=2**(N-1)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        D.append( (2*D[-1]-d0)/2+d0 )

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、降順ソートする
D.sort(reverse=True)

ans=0
for c,d in zip(C,D):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod


Fixed submission:
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        next=(2*D[-1]-d0)*pow(2,mod-2,mod)+d0
        D.append(next%mod)

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、Dは配列を逆順にしたものを足し合わせる
#modを取っているので、Dを降順ソートすると順番が崩れる
ans=0
for c,d in zip(C,D[::-1]):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod

ans=0

for i in range(N):
    l=i
    r=N-i-1
    keisu=N-i
    for k in range(1,keisu+1):
        ans+=2**l*ncr(r,k-1)*k*C[i]

print (ans*2**N)%mod

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N=input()
C=map(int, sys.stdin.readline().split())
C.sort()

mod=10**9+7
D=[]
d0=pow(2,N-1,mod)

#D：係数の配列の作成
for i in range(N):
    if i==0:
        D.append(d0)
    else:
        next=(2*D[-1]-d0)*pow(2,mod-2,mod)+d0
        D.append(next%mod)

#Ci*Diを最小にするため、最小のCiに最大のDiを掛けるため、Dは配列を逆順にしたものを足し合わせる
#modを取っているので、Dを降順ソートすると順番が崩れる
ans=0
for c,d in zip(C,D[::-1]):
    ans+=c*d
    ans%=mod

ans=ans*pow(2,N,mod)

print ans%mod
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import copy

X=input()

C={}    #n円を構成する品物の最小個数の集合

for n in range(1,100):
    org_n=copy.deepcopy(n)
    kosu=0     #n円を構成する品物の最小個数
    for i in range(5,0,-1):     
        kosu+=n/i
        n=n%i   #iで割った余りが残る
        if n==0:
            C[org_n]=kosu
            break


max_kosu=X/100
x=X%100

if max_kosu>=C[x]:
    print 1
else:
    print 0


Fixed submission:
# -*- coding: utf-8 -*-
import copy

X=input()

C={}    #n円を構成する品物の最小個数の集合

for n in range(100):
    org_n=copy.deepcopy(n)
    kosu=0     #n円を構成する品物の最小個数
    for i in range(5,0,-1):     
        kosu+=n/i
        n=n%i   #iで割った余りが残る
        if n==0:
            C[org_n]=kosu
            break

max_kosu=X/100
x=X%100

if max_kosu>=C[x]:
    print 1
else:
    print 0
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append(S[-1]+a)   #累積和

ans=0
for l in range(N):
    for r in range(l+1,min(l+K,N+1)):
        if (S[r]-S[l])%K==0:
            ans+=1
print ans

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: a%K, A)


S=[0]
for i,a in enumerate(A):
        S.append(S[-1]+a)
  
ans=0

i=0
for i in range(N):
    for k in range(1,K+1):
        if i+k<=N:
            if k==(S[i+k]-S[i])%K:
                ans+=1

print ans


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: a%K, A)


S=[0]
for i,a in enumerate(A):
        S.append(S[-1]+a)
  
ans=0

i=0
for i in range(N):
    for k in range(1,K+1):
        if i+k<=N:
            if k==(S[i+k]-S[i])%K:
                ans+=1

print ans


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの集合
i=N
end=False
for _ in range(N):
    if end: break
    for m in range(M,0,-1):
        #print m,i+m
        if 0<=i-m and S[i-m]=="0":
            L.append(m)
            i-=m
            if i==0: end=True
            break
        
if i!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))


Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの集合
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの集合
i=N
end=False
for _ in range(N):
    if end: break
    for m in range(M,-1,-1):
        #print m,i+m
        if 0<=i-m and S[i-m]=="0":
            L.append(m)
            i-=m
            if i==0: end=True
            break
        
if i!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))


Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの集合
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

import sys
N,T=map(int, sys.stdin.readline().split())
AB=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

AB.sort()

N=2005
dp=[ None for _ in range(N) ]
dp[0]=0

for a,b in AB:
    for i in range(N-1,-1,-1):
        if dp[i] is not None and i<T:
                dp[i+a]=max(dp[i+a],dp[i]+b)

print max(dp)


Fixed submission:
# -*- coding: utf-8 -*-

import sys
N,T=map(int, sys.stdin.readline().split())
AB=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

AB.sort()

N=6005
dp=[ None for _ in range(N) ]
dp[0]=0

for a,b in AB:
    for i in range(N-1,-1,-1):
        if dp[i] is not None and i<T:
                dp[i+a]=max(dp[i+a],dp[i]+b)

print max(dp)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
F=map(int, sys.stdin.readline().split())

A.sort()
F.sort(reverse=True)

hq=[]

for x,y in zip(A,F):
    heappush( hq,(-1*x*y,x,y) )


while 0<K:
    v=heappop(hq)
    x=v[1]
    y=v[2]
    x-=1
    K-=1
    heappush( hq,(-1*x*y,x,y) )

print hq[0][0]*-1

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
F=map(int, sys.stdin.readline().split())
A.sort(reverse=True)
F.sort()

max_ans=A[0]*F[-1]

def check(temp_ans):
    if temp_ans<0:
        return False
    k=0
    for a,f in zip(A,F):
        if a*f<=temp_ans: continue
        aa=temp_ans/f
        k+=(a-aa)
        if K<k:
            return False
    else:
        return True

h=max_ans
l=-1

while h-l!=1:
    m=(h+l)/2
    if check(m):
        h=m
    else:
        l=m

print h
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#リバース隣接リスト
I=[ 0 for i in range(N+1) ] #入次数
O=[ 0 for i in range(N+1) ] #出次数
edge=[] #辺の集合
I[0]=None

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    I[t]+=1
    O[s]+=1
    edge.append((s,t))

#トポロジカルソート
L=[]
q=deque()
q.append(1) #startは常に1

while q:
    fro=q.popleft()
    L.append(fro)
    for to in al[fro]:
        I[to]-=1
        if I[to]==0:
            q.append(to)

if len(L)!=N:
    prin

#頂点毎の到達する確立
P=[ 0 for i in range(N+1) ]   #確率
P[1]=1

for x in L:
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        
#頂点毎の期待値
E=[ 0 for i in range(N+1) ]   #期待値

for x in L[::-1]:
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p
#消す辺
ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    #print "del_s,del_t,new_E, :: ",del_s,del_t,new_E,E,E[1]+(new_E-E[del_s])*P[del_s]
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())
al=[ [] for i in range(N+1) ]	#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#リバース隣接リスト
O=[ 0 for i in range(N+1) ] #出次数
edge=[] #辺の集合

for _ in range(M):
    s,t=map(int, sys.stdin.readline().split())
    al[s].append(t)
    rev_al[t].append(s)
    #I[t]+=1
    O[s]+=1
    edge.append((s,t))


#頂点毎の到達する確立
P=[ 0 for i in range(N+1) ]   #確率
P[1]=1
 
for x in range(1,N+1):
    if O[x]!=0:
        p=float(1)/O[x]
        for to in al[x]:
            P[to]+=P[x]*p
        
#頂点毎の期待値
E=[ 0 for i in range(N+1) ]   #期待値

for x in range(N,0,-1):
    for to in rev_al[x]:
        p=float(1)/O[to]
        E[to]+=(E[x]+1)*p


#消す辺
ans=E[1]
for del_s,del_t in edge:
    if O[del_s]-1==0:
        continue
    new_E=float(E[del_s]*O[del_s]-(E[del_t]+1))/(O[del_s]-1)
    #print "del_s,del_t,new_E, :: ",del_s,del_t,new_E,E,E[1]+(new_E-E[del_s])*P[del_s]
    if new_E<E[del_s]:
        ans=min(ans,E[1]-(E[del_s]-new_E)*P[del_s])

print ans