Submission #1213473

#TimeUsernameProblemLanguageResultExecution timeMemory
1213473minhpkPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms328 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b; string s; int f[20][2][11][11][2]; int dp(int i,int idx,int j,int k,int keep){ if (i>=s.size()){ return keep; } if (f[i][idx][j][k][keep]!=-1){ return f[i][idx][j][k][keep]; } f[i][idx][j][k][keep]=0; int max1; if (idx){ max1=s[i]-'0'; }else{ max1=9; } int ans=0; for (int t=0;t<=max1;t++){ if (t==0){ if (k==10){ ans+= dp(i+1,0,10,10,0); }else{ int pre=0; if ((t==k)||(t==j)){ pre=1; } ans+= dp(i+1,(t==max1)&&(idx),k,t,max(keep,pre)); } }else{ int pre=0; if ((t==k)||(t==j)){ pre=1; } ans+= dp(i+1,(t==max1)&&(idx),k,t,max(keep,pre)); } } return f[i][idx][j][k][keep]=ans; } int get(int n){ if (n==-1){ return 0; } s=to_string(n); s='#'+s; memset(f,-1,sizeof f); return dp(1,1,10,10,0); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b; a--; cout << (b-a)-(get(b)-get(a)) << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...