제출 #446151

#제출 시각아이디문제언어결과실행 시간메모리
446151callmepandeyPalindrome-Free Numbers (BOI13_numbers)C++17
0 / 100
2 ms1612 KiB
/* * The way if it's all predetermined * And the way i should go all my life * I swear to go wherever will be * 'Cause there'll be something to see and to find */ #include "bits/stdc++.h" #define ll long long using namespace std; #define check(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename val1> void __f(const char* name, val1&& value) { cout << name << " = " << value << endl; } template <typename val1, typename... values> void __f( const char* names, val1&& value, values&&... multiplevalue) { const char* comma = strchr( names + 1, ','); cout.write(names, comma - names) << " = " << value << " "; __f(comma + 1, multiplevalue...); } ll a , b; string n , m; ll till; ll dp[21][21][2][2][10][10]; ll memo(ll i,ll startedwhen,ll started,ll small,ll last, ll secondlast,string s){ if(i==till) return 1; ll &ans = dp[i][startedwhen][started][small][last][secondlast]; if(ans != -1) return ans; ans = 0; int curr = s[i] - '0'; if(started==0){ ans += memo(i+1,startedwhen,0,0,0,0,s); for(int j = 1;j<=curr;j++){ ans += memo(i+1,i,1,(j<curr),j,last,s); } } else { int x = 9; if(small==0){ x = curr; } if(i - startedwhen==1){ for(int j = 0;j<=x;j++){ if(j==last) continue; ans += memo(i+1,startedwhen,1,(small | (j<curr)),i,last,s); } } else { for(int j = 0;j<=x;j++){ if(j==last or j==secondlast) continue; ans += memo(i+1,startedwhen,1,(small | (j<curr)),i,last,s); } } } return ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b; swap(a , b); while(a){ char add = (char)((a%10) + '0'); n = add + n; a /= 10; } b--; while(b){ char add = (char)((b%10) + '0'); m = add + m; b /= 10; } till = n.size(); memset(dp,-1,sizeof dp); ll ans = memo(0 , 0 , 0 , 0 , 0 , 0 , n); memset(dp,-1,sizeof dp); till = m.size(); if(b > -1) ans -= memo(0,0,0,0,0,0,m); cout << ans << endl; cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...