Submission #44221

#	Time	Username	Problem	Language	Result	Execution time	Memory
44221		neutron_byte	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	1280 KiB

numbers

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int da[20];
int db[20];

ll memo[20][2][2][10][10][2][2];

ll solve(int idx, bool flagA, bool flagB, int pre1, int pre2, bool zero1, bool zero2) {
    if (idx == -1) {
        return 1;
    }

    if (memo[idx][flagA][flagB][pre1][pre2][zero1][zero2] != -1) {
        return memo[idx][flagA][flagB][pre1][pre2][zero1][zero2];
    }

    ll rs = 0;
    for (int d = 0; d <= 9; ++d) {
        if (flagA && d < da[idx]) continue;
        if (flagB && d > db[idx]) continue;
        if ((!zero1 && pre1 == d) || (!zero2 && pre2 == d)) continue;

        bool nzero1;
        if (zero1 && d == 0) nzero1 = true;
        else nzero1 = false;

        rs += solve(idx - 1, flagA && d == da[idx], flagB && d == db[idx], d, pre1, nzero1, zero1);
    }

    return memo[idx][flagA][flagB][pre1][pre2][zero1][zero2] = rs;
}

int main() {
    ll a, b;
    cin >> a >> b;

    fill(da, da + 20, 0);
    fill(db, db + 20, 0);

    for (int i = 0; i < 20; ++i) {
        da[i] = a % 10;
        db[i] = b % 10;
        a /= 10; b /= 10;
    }

    fill(memo[0][0][0][0][0][0], memo[0][0][0][0][0][0] + 32000, -1);
    cout << solve(19, true, true, 0, 0, true, true) << endl;

    return 0;
}

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