제출 #888404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888404		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KiB

numbers

#include "bits/stdc++.h"
using namespace std;
bool START;
void init();
void solve();
bool multitest();
void time_and_memory();
clock_t TIME = clock();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int TEST = 1;
    if (multitest()) cin >> TEST;
    while (TEST--) solve();
    time_and_memory();
}

bool multitest() {
    return 0;
}

void init() {
}

#define int long long

int n, digit[19], dp[19][11][11][2][2];

int DP(int p, int num0, int num1, bool s, bool ok) {
    if (p == n) return ok;
    if (dp[p][num0+1][num1+1][s][ok] != -1)
        return dp[p][num0+1][num1+1][s][ok];

    int loop = max(digit[p], 9LL * s), res = 0;

    for (int i = 0; i <= loop; ++i)
        if (num1 == -1 && i == 0)
            res += DP(p+1, -1, -1, 1, 0);
        else if (i == num0 || i == num1)
            res += DP(p+1, num1, i, s | (i < loop), 1);
        else
            res += DP(p+1, num1, i, s | (i < loop), ok);

    return dp[p][num0+1][num1+1][s][ok] = res;
}

int ac(int x) {
    if (x < 0) return 0;

    n = 0;
    for (; x > 0; x /= 10) digit[n++] = x % 10;
    reverse(digit, digit+n);

    memset(dp, -1, sizeof(dp));

    return DP(0, -1, -1, 0, 0);
}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << (b - a + 1) - (ac(b) - ac(a - 1));
}

bool END;
void time_and_memory() {
    cerr << "\nUsed: " << clock() - TIME << " ms, ";
    cerr << fixed << setprecision(3);
    cerr << fabs((&START - &END) / 1048576.0) << " MB\n\n";
}

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