Submission #708405

#	Time	Username	Problem	Language	Result	Execution time	Memory
708405		Johann	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	4128 ms	15572 KiB

vault

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

vi calcShifts(int a)
{
    vi ans;
    int i = 0;
    while ((1 << i) <= a)
    {
        a -= (1 << i);
        ans.push_back(i++);
    }
    while (i > 0)
        if ((1 << --i) <= a)
            ans.push_back(i), a -= (1 << i);
    return ans;
}

int calcDP(vi &A, ll L, ll M)
{
    int an = accumulate(A.begin(), A.begin() + M, 0);
    int ap = accumulate(A.begin() + M + 1, A.begin() + 2 * M + 1, 0);

    int MAXSIZE = 2 * M * max(an, ap) + 2;

    vi dp(MAXSIZE, -1);
    ll center = MAXSIZE / 2;
    dp[center] = A[M];
    for (int foo = 0; foo < 2; ++foo)
    {
        reverse(all(A)), reverse(all(dp));
        for (ll m = 1; m <= M; ++m)
        {
            ll maxNum = A[m + M];
            vi shifts = calcShifts(maxNum);
            for (int i : shifts)
            {
                ll amount = (1 << i);
                ll d = amount * m;
                for (int j = sz(dp) - 1; j >= d; --j)
                    dp[j] = max(dp[j], (dp[j - d] != -1) ? dp[j - d] + amount : -1);
            }
        }
    }

    if (0 <= center + L && center + L < sz(dp))
        return dp[center + L];
    else
        return -1;
}

pii calcPref(vi &A, int M, int L, ll &pref, ll &tmpans) // find first Prefix position { i, idx } with pref >= L, or { sz(A)-1 = 2 * M, A[2 * M] }
{
    int i = 0;
    tmpans = 0, pref = 0;
    for (; i < M; ++i)
        tmpans += A[i], pref += A[i] * (i - M);
    if (pref >= L)
        return {i, 0};
    while (i < sz(A) && pref + A[i] * (i - M) < L)
    {
        pref += A[i] * (i - M);
        tmpans += A[i];
        ++i;
    }
    if (i == sz(A))
        return {i - 1, A[i - 1]};

    ll delta = L - pref;
    assert(delta >= 0); // The expectation after the while loop is, that one is able to forfill this shit with the A[i] * (i - M) stuff
    int l = 0, r = A[i], m;
    while (l < r)
    {
        m = (l + r) / 2;
        ll v = (i - M) * m;
        if (v < delta)
            l = m + 1;
        else
            r = m;
    }
    pref += l * (i - M);
    tmpans += l;

    return {i, l};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll M, L;
    cin >> M >> L;
    vi A(2 * M + 1);
    for (int i = 0; i < sz(A); ++i)
        cin >> A[i];

    // cout << calcDP(A, L, M) << endl;

    vi B(sz(A), 0);
    ll dpMax = 0, dpMin = 0; // Obere Grenze und untere Grenze für das davon induzierte DP
    for (int i = 0; i < sz(B); ++i)
    {
        if (i == M)
        {
            B[i] = A[i];
            A[i] = 0;
            continue;
        }
        B[i] = min(M - 1, A[i]);
        A[i] -= B[i];
        dpMax = max(dpMax, dpMax + B[i] * (i - M));
        dpMin = min(dpMin, dpMin + B[i] * (i - M));
    }

    vi C;
    for (ll b : B)
        C.push_back(b);
    ll li, lidx, ri, ridx, pref, tmpans;
    tie(ri, ridx) = calcPref(A, M, L - dpMin + 1, pref, tmpans);
    tie(li, lidx) = calcPref(A, M, L - dpMax, pref, tmpans);

    for (int i = li; i < ri; ++i)
    {
        C[i] += A[i] - lidx;
        lidx = 0;
    }
    C[ri] += ridx - lidx;

    ll ans = -1;
    ll tmp = calcDP(C, L - pref, M);
    if (tmp != -1)
        ans = tmpans + tmp;

    if (ans == -1)
        cout << "impossible\n";
    else
        cout << ans << "\n";

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10