Submission #711941

#	Time	Username	Problem	Language	Result	Execution time	Memory
711941		Johann	Uplifting Excursion (BOI22_vault)	C++14	100 / 100	1448 ms	1764 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(ll a)
{
    vi ans;
    ll i = 0;
    while ((1LL << i) <= a)
    {
        a -= (1LL << i);
        ans.push_back(i++);
    }
    while (i > 0)
        if ((1LL << --i) <= a)
            ans.push_back(i), a -= (1 << i);
    return ans;
}

vi dp;
ll center;
void initDP(ll M, ll zero)
{
    center = M * M;
    dp.assign(2 * center + 1, INT_MIN);
    assert(0 <= center + zero && center + zero < sz(dp));
    dp[center + zero] = 0;
}
void addToDP(ll lift, ll maxNum)
{
    ll f = (maxNum < 0) ? -1 : 1;
    vi shifts = calcShifts(abs(maxNum));
    for (int i : shifts)
    {
        ll amount = f * (1 << i);
        ll d = amount * lift;
        if (d > 0)
        {
            for (int j = sz(dp) - 1; j >= d; --j)
                dp[j] = max(dp[j], (dp[j - d] != INT_MIN) ? dp[j - d] + amount : INT_MIN);
        }
        else
        {
            for (int j = 0; j < sz(dp) - abs(d); ++j)
                dp[j] = max(dp[j], (dp[j - d] != INT_MIN) ? dp[j - d] + amount : INT_MIN);
        }
    }
}

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];

    ll totalSum = 0;
    for (int i = 0; i < sz(A); ++i)
        totalSum += (i - M) * A[i];

    if (totalSum < L)
    {
        reverse(all(A));
        totalSum *= -1;
        L *= -1;
    }

    // find last Prefix position { i, idx } with pref <= L, or { sz(A)-1 = 2 * M, A[2 * M] }

    int i = 0;
    ll tmpans = 0, pref = 0;
    vpii toadd;
    for (; i < M; ++i)
    { // taking all negative values
        tmpans += A[i];
        pref += A[i] * (i - M);
        toadd.push_back({i - M, max(-A[i], -M)});
    }

    while (i < sz(A) && pref + A[i] * (i - M) < L)
    {
        pref += A[i] * (i - M);
        tmpans += A[i];
        toadd.push_back({i - M, max(-A[i], -M)});
        ++i;
    }
    if (i == sz(A) || L - pref < 0)
    {
        cout << "impossible\n";
        return 0;
    }

    assert(L - pref >= 0); // The expectation after the while loop is, that one is able to forfill this shit with the A[i] * (i - M) stuff
    ll l = (L - pref) / (i - M);
    pref += l * (i - M);
    tmpans += l;

    toadd.push_back({i - M, max(-l, -M)});
    toadd.push_back({i - M, min(A[i] - l, M)});
    for (int j = i + 1; j < sz(A); ++j)
        toadd.push_back({j - M, min(A[j], M)});

    initDP(M, pref - L);
    for (pii add : toadd)
        addToDP(add.first, add.second);

    ll ans = INT_MIN;
    if (dp[center] != INT_MIN)
        ans = tmpans + dp[center];

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

    return 0;
}

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