Query regrading SPOJ MBALL

Revision en1, by ayushexel, 2016-07-24 05:42:36

problem link : http://www.spoj.com/problems/MBALL/

my solution :

include

include <memory.h>

using namespace std;

long long dp[100002][6];

long long solve(long long b,long long c){ if(b==0) return 1; if(b<0||c==5) return 0; if(dp[b][c]!=-1){ return dp[b][c]; } long long ret = 0; if(c<=0){ for(long long i=2;i<=b;i+=2) ret += solve(b-i,1); }

if(c<=1){ for(long long i=3;i<=b;i+=3) ret += solve(b-i,2); }

if(c<=2){ for(long long i=6;i<=b;i+=6){ ret += solve(b-i,3); } }

if(c<=3){ for(long long i=7;i<=b;i+=7){ ret += solve(b-i,4); } }

if(c<=4){ for(long long i=8;i<=b;i+=8){ ret += solve(b-i,5); } }

return dp[b][c] = ret; }

int main() { int n; cin>>n; while(n--){ memset(dp,-1,sizeof(dp)); int s; cin>>s; cout << solve(s,0) << endl; } return 0; }

The code is working fine but on submitting i'm getting "time limit exceeded" error . I don't want to use iterative approach . So, how can the time limit be reduced without using iterative DP ?

Tags #algorithms, dynamic programming, recursion, spoj

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ayushexel 2016-07-24 09:30:18 28
en2 English ayushexel 2016-07-24 05:43:08 18
en1 English ayushexel 2016-07-24 05:42:36 1053 Initial revision (published)