# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
217782 | vonatlus | Trol (COCI19_trol) | C++14 | 10 ms | 452 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |