#include <iostream>
#include <string.h>
using namespace std;
#define ll long long int
ll dp[2020][11];
int twop[11]={1,2,4,8,16,32,64,128,256,512,1024};
int m;
ll solve(int last,int rem){
if(rem==0&&last<=m)
return 1;
if(rem>0&&last>m)
return 0;
if(dp[last][rem]!=-1)
return dp[last][rem];
ll ans=0;
for(int i=2*last;i*twop[rem-1]<=m;i++){
ans+=solve(i,rem-1);
}
dp[last][rem]=ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t,n;
cin >> t;
for(int i=1;i<=t;i++){
memset(dp,-1,sizeof(dp));
cin >> n >> m;
ll ans=0;
for(int i=1;i*twop[n-1]<=m;i++)
ans+=solve(i,n-1);
cout << "Data set "<< i << ": " << n << " " << m << " " << ans << endl;
}
return 0;
}
Hi,
I tried a top-down dp for the problem http://www.spoj.com/problems/GNYR04C/ (Lennys Lucky Lotto Lists) with my code for the same above.
I am getting a TLE even after limiting the iterations in the for loop.
Could someone explain the how to further optimize to avoid the TLE?