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 .
__author__ = "Achut" s,n = map(int,raw_input().strip().split()) a = *(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)