Query regrading SPOJ MBALL

Revision en3, by ayushexel, 2016-07-24 09:30:18

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

my solution :

#include <iostream>
#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;
memset(dp,-1,sizeof(dp));
while(n--){

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)