Submission #512287

#	Time	Username	Problem	Language	Result	Execution time	Memory
512287		hoanghq2004	Trol (COCI19_trol)	C++14	50 / 50	62 ms	364 KiB

trol

#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 (stderr)

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 / 50