답안 #512287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512287	2022-01-16T08:51:46 Z	hoanghq2004	Trol (COCI19_trol)	C++14	50 / 50	62 ms	364 KB

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

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

#	결과	실행 시간	메모리	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