Problem p03290 (python)

Fixed submission:
D,G=map(int,raw_input().split())

A=[map(int,raw_input().split()) for i in range(D)]

N=1000
dp=[ [ float("-inf") for i in range(N+100)]  for j in range(D) ] 

p=A[0][0]
c=A[0][1]


for i in range(1,p+1):
	if i==p: dp[0][i]=i*100+c
	else: dp[0][i]=i*100

for i in range(D):
	dp[i][0]=0



for k in range(1,D):
	p=A[k][0]    # number of problems per line
	c=A[k][1]    # bonus

	for i in range(N):		         #dp[k][i]
		for j in range(1,p+1):    #number of problems per line
			dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100, dp[k-1][i+j] )
		dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100+c,dp[k-1][i+j] )



for idx,i in enumerate(dp[D-1]):
	if i>=G:
		print idx
		quit()

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

D,G=map( int, raw_input().split() )
P=[ map( int, raw_input().split() ) for i in range(D) ] 

N=10**5+2000
dp= [   [ float("inf") for i in range(N+1)] for idx in range(D+1)  ]
dp[0][0]=0

for idx, x  in enumerate(P):
	m=idx+1	#money
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[idx][i]!=float("inf"):
			for j in range(p,-1,-1):	# j= problems count   , idx = score of a problem
				if j==p:
					dp[idx+1][i+m*j+c]=min( dp[idx+1][i+m*j+c] , dp[idx][i]+j )
				else:
					dp[idx+1][i+m*j]=min( dp[idx+1][i+m*j] , dp[idx][i]+j )


ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[-1][i])

print ans

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

D,G=map( int, raw_input().split() )
P=[ map( int, raw_input().split() ) for i in range(D) ] 

N=10**5
dp= [ float("inf") for i in range(N+1)]
dp[0]=0

for idx, x  in enumerate(P):
	idx+=1
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[i]!=float("inf"):
			for j in range(p+1):	# j= problems count   , idx = score of a problem
				dp[i+idx*j]=min( dp[i+idx*j] , dp[i]+j )
				if j==p:
					dp[i+idx*j+c]= min( dp[i+idx*j+c], dp[ i+idx*j ] )


ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[i])

print ans

Buggy submission (verdict: Runtime Error):
D,G=map(int,raw_input().split())

A=[map(int,raw_input().split()) for i in range(D)]

N=1000
dp=[ [ float("-inf") for i in range(N+100)]  for j in range(D) ] 

p=A[0][0]
c=A[0][1]


for i in range(1,p+1):
	if i==p: dp[0][i]=i*100+c
aa	else: dp[0][i]=i*100

for i in range(D):
	dp[i][0]=0



for k in range(1,D):
	p=A[k][0]    # number of problems per line
	c=A[k][1]    # bonus

	for i in range(N):		         #dp[k][i]
		for j in range(1,p+1):    #number of problems per line
			dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100, dp[k-1][i+j] )
		dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100+ac,dp[k-1][i+j] )



for idx,i in enumerate(dp[D-1]):
	if i>=G:
		print idx
		quit()

Buggy submission (verdict: Runtime Error):
D,G=map(int,raw_input().split())
G=G/100

P=[map(int,raw_input().split()) for i in range(D)]

S=6000

dp=[ [ float("inf") for i in range(S)]  for j in range(D) ] 
a=P[0][0]
b=P[0][1]/100

for i in range(a+1):
	if i==a: dp[0][i+b]=i
	else: dp[0][i]=i

for j in range(D): dp[j][0]=0


for i in range(1,D):
	a=P[i][0]
	b=P[i][1]/100


	for s in range(S):
		for k in range(1,a):
			if s-(k*(i+1)) >=0:
				dp[i][s]=min( dp[i-1][s-(k*(i+1))]+k, dp[i-1][s] )
		if s-( a*(i+1)+b )>=0:
			dp[i][s]=min( dp[i-1][s-( a*(i+1)+b ) ]+a, dp[i-1][s] )

#print dp	
print dp[D-1][G]

Buggy submission (verdict: Runtime Error):
D,G=map(int,raw_input().split())

P=[map(int,raw_input().split()) for i in range(D)]

S=6000

dp=[ [ float("inf") for i in range(S)]  for j in range(D) ] 
a=P[0][0]
b=P[0][1]/100

for i in range(a+1):
	if i==a: dp[0][i+b]=i
	else: dp[0][i]=i

for j in range(D): dp[j][0]=0


for i in range(1,D):
	a=P[i][0]
	b=P[i][1]/100


	for s in range(S):
		for k in range(1,a):
			if s-(k*(i+1)) >=0:
				dp[i][s]=min( dp[i-1][s-(k*(i+1))]+k, dp[i-1][s] )
		if s-( a*(i+1)+b )>=0:
			dp[i][s]=min( dp[i-1][s-( a*(i+1)+b ) ]+a, dp[i-1][s] )

	
ans=float("inf")
for i in range(G/100,S):
	ans=min(ans,dp[D-1][i] )

print ans

Buggy submission (verdict: Runtime Error):
D,G=map(int,raw_input().split())

P=[map(int,raw_input().split()) for i in range(D)]

S=6000

dp=[ [ float("inf") for i in range(S)]  for j in range(D) ] 
c=P[0][0]
s=P[0][1]

for i in range(c+1):
	if i==c: dp[0][i+s/100]=i
	else: dp[0][i]=i

for j in range(D): dp[j][0]=0


for i in range(1,D):
	a=P[i][0]
	b=P[i][1]/100

	for k in range(1,a):
		for s in range(S):
			if s-(k*(i+1)) >=0:
				dp[i][s]=min( dp[i-1][s-(k*(i+1))]+k, dp[i-1][s] )
	for s in range(S):
		if s-( a*(i+1)+b )>=0:
			dp[i][s]=min( dp[i-1][s-( a*(i+1)+b ) ]+a, dp[i-1][s] )

	
ans=float("inf")
for i in range(G/100,S):
	ans=min(ans,dp[D-1][i] )

print ans