제출 #217885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217885		vonatlus	Trol (COCI19_trol)	C++14	50 / 50	10 ms	384 KiB

trol

/// 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[2][19][175];

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());
    int sz = sz(num);
    for (ll d = 0; d < num[0]; ++d) 
        dp[0][0][d]++;
    dp[1][0][num[0]] = 1;
    for (int i = 1; i < sz; ++i) {           
        for (int sum = 165; ~sum; --sum) {
            for (int d = 0; d < 10; ++d) {        
                if (d == num[i])
                    dp[1][i][sum+d] += dp[1][i-1][sum];
                if (d < num[i])                         
                    dp[0][i][sum+d] += dp[1][i-1][sum];    
                dp[0][i][sum+d] += dp[0][i-1][sum];    
            }
        }                         
    }
    ll res = 0;
    for (int sum = 1; sum <= 165; ++sum) 
        res += (dp[0][sz-1][sum]+dp[1][sz-1][sum]) * 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;
}

• Subtask 1: 50 / 50