Here is the link to the problem : https://www.spoj.com/problems/RPLB/

Here is my code however it is giving tle:

include <bits/stdc++.h>

using namespace std; int dp[20001][20001]; int knapsack(int n,int s,vectora) { if(n <= 0 || s<0) { return 0; } if(dp[n][s]!=-1) { return dp[n][s]; } if(a[n-1]<=s) { return dp[n][s] = max(a[n-1]+knapsack(n-2,s-a[n-1],a),knapsack(n-1,s,a)); } else { return dp[n][s] = knapsack(n-1,s,a); } }

int main() { // your code goes here int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int n,s; scanf("%d%d",&n,&s); vectora(n); for(int i=0;i<n;i++) { int num; scanf("%d",&num); a[i] = num; } memset(dp,-1,sizeof(dp)); int ans = knapsack(n,s,a); //cout<<ans<<endl; printf("Scenario #%d: %d\n",i,ans); } }

Thanks:)