제출 #1333921

#제출 시각아이디문제언어결과실행 시간메모리
1333921gelastropodPalindrome-Free Numbers (BOI13_numbers)C++20
10 / 100
2 ms584 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;

string s;

vector<vector<vector<int>>> mem;
vector<int> mem1;

int dp(int n, int d1, int d2) {
    if (n == -1) return 0;
    if (mem[n][d1][d2] != -1) return mem[n][d1][d2];
    int res = 0;
    for (int i = 0; i < 10; i++) {
        if (i == d1 || i == d2) res += pow(10, n);
        else res += dp(n - 1, i, d1);
    }
    return mem[n][d1][d2] = res;
}

int dp1(int n) {
    if (n == -1) return 0;
    if (mem1[n] != -1) return mem1[n];
    int res = 0;
    for (int i = 0; i < s[n] - '0'; i++) {
        if (i == s[n + 1] - '0' || i == s[n + 2] - '0') res += pow(10, n);
        else res += dp(n - 1, i, s[n + 1] - '0');
    }
    if (s[n] - '0' == s[n + 1] - '0' || s[n] - '0' == s[n + 2] - '0') {
        string s1 = (n == 0 ? "1" : s.substr(0, n));
        reverse(s1.begin(), s1.end());
        res += stoi(s1);
    }
    else res += dp1(n - 1);
    return mem1[n] = res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    mem.resize(18, vector<vector<int>>(11, vector<int>(11, -1)));
    mem1.resize(18, -1);
    int n1, n2;
    cin >> n1; n1--;
    s = to_string(n1);
    reverse(s.begin(), s.end());
    int s1 = s.size();
    s += string(20 - s.size(), ':');
    int res1 = dp1(s1 - 1);
    for (int i = 0; i < 18; i++) {
        mem1[i] = -1;
        for (int j = 0; j < 11; j++) for (int k = 0; k < 11; k++) mem[i][j][k] = -1;
    }
    cin >> s;
    n2 = stoi(s);
    reverse(s.begin(), s.end());
    s1 = s.size();
    s += string(20 - s.size(), ':');
    int res2 = dp1(s1 - 1);
    cout << n2 - n1 - res2 + res1 << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...