Submission #2705912

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e4 + 5;
typedef long long ll;
typedef pair<ll, ll> Pair;

vector<Pair> v, w;
vector<ll> A;
ll p10[20];

vector<Pair> best(vector<Pair> v)
{
    vector<Pair> ans;
    sort(v.begin(), v.end());

    ll l = -1, r = -1;
    for(auto it : v)
        if(it.first <= r)
            r = max(r, it.second);
        else
        {
            if(l != -1) ans.push_back({l, r});
            l = it.first;
            r = it.second;
        }
    ans.push_back({l, r});
    return ans;
}

bool solve(int p, int c)
{
    w.clear();
    w.push_back({p10[p] * c, p10[p] * (c+1) - 1});

    ll x, y;
    for(auto val : A)
    {
        v.clear();
        for(auto seg : w)
        {
            x = seg.first;
            y = seg.second;
            v.push_back({x, y});

            val %= p10[p+1];
            x -= val;
            y -= val;

            if(x<=0 && y>=0) return 1;

            if(x<0 && y<0) x += p10[p+1], y += p10[p+1];
            v.push_back({x, y});
        }

        w = best(v);
    }

    return 0;
}

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    int i, c, ans = 0, n;

    cin >> n;
    A.resize(n);
    for(auto &it : A) cin >> it;

    p10[0] = 1;
    for(i=1; i<=17; ++i) p10[i] = (ll) p10[i-1] * 10;

    for(i=0; i<17; ++i)
        for(c=9; c; --c)
            if(solve(i, c))
            {
                ans += c;
                break;
            }
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result