Submission #1213036

#TimeUsernameProblemLanguageResultExecution timeMemory
1213036i_love_springPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms1356 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array ll dp[20][12][12][12][2][2]; string s; bool has_pal(int a,int b,int c) { if (a != -1 && b != -1 && a == b) return true; if (a != -1 && c != -1 && a == c) return true; if (b != -1 && c != -1 && b == c) return true; return false; } ll get(int pos,int a,int b,int c,bool tight,bool zero) { if (pos == s.size()) return 1; ll& res = dp[pos][a + 1][b + 1][c + 1][tight][zero]; if (res != -1) { return res; } res = 0; int limit = (tight ? s[pos] - '0' : 9); for (int d = 0; d <= limit;d++) { int na = b,nb = c,nc = d; bool new_zero = zero && (d == 0); bool new_tight = tight && (d == limit); if (new_zero) { na = -1 , nb = -1 , nc = -1; } if (!new_zero && has_pal(na,nb,nc)) continue; res += get(pos + 1,na,nb,nc,new_tight,new_zero); } return res; } ll get(ll y) { s = to_string(y); memset(dp,-1,sizeof(dp)); return get(0,-1,-1,-1,true,true); } void solve() { ll x,y; cin >> x >> y; cout << get(y) - get(x - 1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while (t--) { solve(); cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...