Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

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

Revision en2, by taklo, 2019-06-12 15:06:34

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)