Help --Getting TLE Verdict in Digit DP Problem even after memoization

Revision en1, by taklo, 2019-06-12 15:05:28

I Came to know about Digit DP from this blog https://codeforces.com/blog/entry/53960 and I Tried the following problem on DIGIT DP as given in the blog https://vjudge.net/problem/LightOJ-1068

here is my code

Your code here...
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
vector<int > num;
void convert(ll n){
vector<int > g;
while(n>0){
g.push_back(n%10);
n/=10;
}
for(int i=g.size()-1;i>=0;i--) num.push_back(g[i]);
}
ll a,b,k;
ll DP[20][200][200][2];
ll call(int pos,int nmodk,int digmodk,int flag){
if(pos==num.size()){
if(nmodk%k==0 && digmodk%k==0)
return 1;
return 0;
}
if(DP[pos][nmodk][digmodk][flag]!=-1)
return DP[pos][nmodk][digmodk][flag];
int lmt=9;
if(!flag)
lmt=num[pos];
int ans=0;
for(int dgt=0;dgt<=lmt;dgt++){
int nflag=flag;
int nnmodk=(((nmodk%k)*(10%k))%k+dgt%k)%k;
int ddigmodk=(digmodk%k+dgt%k)%k;
if(flag==0 && dgt<lmt) nflag=1;
ans+=call(pos+1,nnmodk,ddigmodk,nflag);
}
DP[pos][nmodk][digmodk][flag]=ans;
return ans;
}
ll solve(ll b){
num.clear();
memset(DP,-1,sizeof(DP));
convert(b);
return call(0,0,0,0);
}
int main(){
ll t;
cin>>t;
int p=0;
while(t--){
cin>>a>>b>>k;
cout<<"Case "<<p<<": "<<solve(b)-solve(a-1);
p++;
}
return 0;
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en2 taklo 2019-06-12 15:06:34 41
en1 taklo 2019-06-12 15:05:28 1425 Initial revision (published)