제출 #217782

#제출 시각아이디문제언어결과실행 시간메모리
217782vonatlusTrol (COCI19_trol)C++14
50 / 50
10 ms452 KiB
/// wa ^3^ #pragma GCC optimize("O3") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() using namespace std; using ll = long long; using pii = pair<int, int>; const int MOD = 1e9+7; const int INF32 = 1e9 + 1e2; void stndrtn() { #ifdef accepted freopen(".in", "r", stdin); #endif } const bool flag = 1; ll dp[19][210][2]; ll f(ll sum) { ll res = 0; for (; sum; sum /= 10) res += sum % 10; if (res > 9) res = f(res); return res; } ll get(ll x) { if (x == 0) return 0; vector<int> num; while (x) { num.pb(x%10ll); x /= 10ll; } reverse(num.begin(), num.end()); for (ll d = 0; d < num[0]; ++d) { dp[0][d][0]++; } dp[0][num[0]][1] = 1; for (int i = 1; i < sz(num); ++i) { for (int sum = 200; ~sum; --sum) { for (int d = 0; d < 10; ++d) { if (d == num[i]) dp[i][sum+d][1] += dp[i-1][sum][1]; dp[i][sum+d][0] += dp[i-1][sum][0]; if (d < num[i]) dp[i][sum+d][0] += dp[i-1][sum][1]; } } } ll res = 0; for (int sum = 1; sum <= 200; ++sum) { res += (dp[sz(num)-1][sum][0]+dp[sz(num)-1][sum][1]) * f(sum); } memset(dp, 0, sizeof(dp)); return res; } void maincode() { ll l, r; cin >> l >> r; cout << get(r) - get(l-1) << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), stndrtn(); int ts = 1; if (flag) cin >> ts; while (ts--) maincode(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...