Submission #1171483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171483		nguyenkhangninh99	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	584 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
  
#define int long long

int dp[20][11][11][2][2][2];
string s;
 
int solvedp(int pos, int last2, int last1, bool zero, bool palin, bool lower){
    if(pos == s.size()) return !palin;

    int &res = dp[pos][last2][last1][zero][palin][lower];
    if (res != -1) return res;

    res = 0;
    int lim = (lower ? s[pos] - '0' : 9);
    for(int i = 0; i <= lim; i++){
        zero |= (i != 0);
        if(zero) res += solvedp(pos + 1, last1, i, zero, palin | (i == last1) | (i == last2), lower && (i == lim));
        else res += solvedp(pos + 1, last2, last1, zero, palin, lower && (i == lim));

    }
    return res;
}
 
int f(int x){
    s = to_string(x);
    memset(dp, -1, sizeof(dp));
    return solvedp(0, 10, 10, 0, 0, 1);
}
 
void solve(){
    int l, r; cin >> l >> r;
    cout << f(r) - f(l - 1);
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    solve();
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75