oj.uz

Submission #512287

# Submission time Handle Problem Language Result Execution time Memory
512287 2022-01-16T08:51:46 Z hoanghq2004 Trol (COCI19_trol) C++14
50 / 50
 62 ms 364 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int g[200];
vector <int> dgt;
long long f[20][200][2];

long long calc(int i, int s, int smaller) {
    if (i == dgt.size()) return f[i][s][smaller] = (s == 0);
    if (f[i][s][smaller] != -1) return f[i][s][smaller];
    f[i][s][smaller] = 0;
    for (int c = 0; c <= (!smaller ? dgt[i] : 9); ++c)
        if (s >= c) f[i][s][smaller] += calc(i + 1, s - c, smaller || (c < dgt[i]));
    return f[i][s][smaller];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    for (int i = 1; i <= 162; ++i) {
        int j = 0;
        for (int x = i; x; x /= 10) j += x % 10;
        if (i == j) g[i] = i;
        else g[i] = g[j];
    }
    int q;
    cin >> q;
    while (q--) {
        long long L, R;
        cin >> L >> R;
        long long ans = 0;
        for (long long x = R; x; x /= 10) dgt.push_back(x % 10);
        reverse(dgt.begin(), dgt.end());
        memset(f, -1, sizeof(f));
        for (int i = 1; i <= 162; ++i) ans += calc(0, i, 0) * g[i];
        dgt.clear();
        for (long long x = L - 1; x; x /= 10) dgt.push_back(x % 10);
        reverse(dgt.begin(), dgt.end());
        memset(f, -1, sizeof(f));
        for (int i = 1; i <= 162; ++i) ans -= calc(0, i, 0) * g[i];
        dgt.clear();
        cout << ans << '\n';
    }
}

Compilation message

trol.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
trol.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
trol.cpp: In function 'long long int calc(int, int, int)':
trol.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (i == dgt.size()) return f[i][s][smaller] = (s == 0);
      |         ~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 300 KB Output is correct
2 Correct 23 ms 332 KB Output is correct
3 Correct 62 ms 356 KB Output is correct
4 Correct 28 ms 364 KB Output is correct
5 Correct 56 ms 332 KB Output is correct