getting TLE for KNAPSACK?

link to question is http://www.spoj.com/problems/KNAPSACK/

this is a basic 0-1 knapsack problem , which gets TLE in Python 2.7

i implemented in 1D array not a 2D array even then it gets TLE . c++ gets accepted , please dont tell me that python is slow ,time is relaxed so that shouldn’t be the reason .

code :

__author__ = "Achut"

s,n = map(int,raw_input().strip().split())
a = [0]*(s+1)
while n :
    n = n-1
    x,y = map(int,raw_input().strip().split())
    if a <= 0 or y <= 0 or x > s:
        continue
    for i in range(s-x,0,-1):
        if a[i] != 0:
            a[i+x] = max(a[i]+y,a[i+x])
    a[x] = max(a[x],y)
    #print a
print max(a)
1 Like