Submission #1121358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121358		coolboy19521	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	2 ms	504 KiB

numbers

#include"bits/stdc++.h"
using namespace std;

using ll = long long;

const int mxN = 19;
const int mxD = 11;

ll dp[mxN][mxD][mxD][2];

ll go(string& S, int i, int j, int k, int f) {
    if ("-1" == S) {
        return 0;
    }
    if ((int)size(S) == i) {
        return 1;
    }
    if (0 <= dp[i][j][k][f]) {
        return dp[i][j][k][f];
    }
    ll& val = dp[i][j][k][f];
    val = 0;
    if (0 == k) {
        val += go(S, i + 1, j, k, 0);
    }
    int st = 1 + (1 > k);
    int d = S[i] - '0' + 1;
    for (int l = st; l < mxD; l ++) {
        if (l ^ j && l ^ k) {
            if (l < d || 0 == f) {
                val += go(S, i + 1, k, l, 0);
            } else if (l == d) {
                val += go(S, i + 1, k, l, 1);
            }
        }
    }
    return val;
}

main() {
    ll a;
    string B;
    cin >> a >> B;

    string A = to_string(a - 1);

    memset(dp, 0xc0, sizeof(dp));
    ll ans = go(B, 0, 0, 0, 1);
    memset(dp, 0xc0, sizeof(dp));
    ans -= go(A, 0, 0, 0, 1);

    cout << ans << endl;
}

Compilation message (stderr)

numbers.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

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