Help --Getting TLE Verdict in Digit DP Problem even after memoization
Difference between en1 and en2, changed 41 character(s)
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
 I am Getting TLE on it Please Help Me!!!

~~~~~↵
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 English taklo 2019-06-12 15:06:34 41
en1 English taklo 2019-06-12 15:05:28 1425 Initial revision (published)