59102023-10-05 15:08:03TuruTamasSzivárványszámokcpp17Elfogadva 45/456ms4792 KiB
#include "bits/stdc++.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstddef>
#include <ostream>
#include <regex>
#include <set>
#include <string>
#include <type_traits>
#include <vector>
using namespace std;

#define ll unsigned long long

string s;
ll r = 0;
int init_size;
int cur_size;
int ind = -1;
string cur;
vector<vector<vector<ll>>> cache;

void recurse(bool past_mid, bool any, int lastval) {
    ind++;
    // if (ind != 0) cur.push_back(lastval + '0');
    if (ind == cur_size) {
        r += any;
        ind--;
        // cout << cur << " " << cur.size() << endl;
        // cur.pop_back();
        return;
    }
    ll& val = cache[past_mid + 2*any][lastval][ind];
    if (val != -1) {
        r += val;
        ind--;
        // cur.pop_back();
        return;
    }
    ll old_val = r;
    int mini = ind == 0, maxi;
    int c = s[ind] - '0';
    if (!past_mid && !any) {
        maxi = c;
    }
    else if (!past_mid && any) {
        maxi = 9;
    }
    else if (past_mid && !any) {
        maxi = min(c, lastval);
    }
    else if (past_mid && any) {
        maxi = lastval;
    }
    for (int i = mini; i <= maxi; i++) {
        bool pm = past_mid || i < lastval;
        bool a = any || i < c;
        recurse(pm, a, i);
    }
    // if (ind != 0) cur.pop_back();
    val = r-old_val;
    ind--;
}

int main() {
    cin >> s;
    cur_size = init_size = s.size();
    cache.assign(4, vector<vector<ll>>(10, vector<ll>(cur_size, -1)));
    recurse(false, false, 0);
    while (--cur_size) {
        cache.assign(4, vector<vector<ll>>(10, vector<ll>(cur_size, -1)));
        recurse(false, true, 0);
    }
    cout << r + 1 << endl;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/03ms1812 KiB
2Elfogadva0/03ms2060 KiB
3Elfogadva0/04ms2284 KiB
4Elfogadva1/13ms2316 KiB
5Elfogadva1/13ms2528 KiB
6Elfogadva1/13ms2924 KiB
7Elfogadva1/12ms2980 KiB
8Elfogadva1/12ms2980 KiB
9Elfogadva1/13ms3168 KiB
10Elfogadva1/13ms3472 KiB
11Elfogadva1/12ms3280 KiB
12Elfogadva1/13ms3472 KiB
13Elfogadva2/23ms3604 KiB
14Elfogadva2/22ms3688 KiB
15Elfogadva2/23ms3800 KiB
16Elfogadva2/23ms3988 KiB
17Elfogadva1/13ms4124 KiB
18Elfogadva2/24ms4268 KiB
19Elfogadva2/24ms4492 KiB
20Elfogadva2/24ms4792 KiB
21Elfogadva3/36ms4732 KiB
22Elfogadva2/23ms4640 KiB
23Elfogadva2/23ms4732 KiB
24Elfogadva2/23ms4664 KiB
25Elfogadva2/24ms4740 KiB
26Elfogadva2/24ms4768 KiB
27Elfogadva2/26ms4780 KiB
28Elfogadva2/26ms4756 KiB
29Elfogadva2/26ms4764 KiB
30Elfogadva2/26ms4736 KiB