Submission #217883

#	Time	Username	Problem	Language	Result	Execution time	Memory
217883		vonatlus	Trol (COCI19_trol)	C++14	50 / 50	11 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[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());
    int sz = sz(num);
    for (ll d = 0; d < num[0]; ++d) 
        dp[0][d][0]++;
    dp[0][num[0]][1] = 1;
    for (int i = 1; i < sz; ++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-1][sum][0]+dp[sz-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;
}

• Subtask 1: 50 / 50