Submission #708405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708405	2023-03-11T17:23:42 Z	Johann	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	4128 ms	15572 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	80 ms	1344 KB	Output is correct
6	Correct	89 ms	1352 KB	Output is correct
7	Correct	23 ms	852 KB	Output is correct
8	Correct	81 ms	1236 KB	Output is correct
9	Correct	187 ms	2132 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	80 ms	1344 KB	Output is correct
6	Correct	89 ms	1352 KB	Output is correct
7	Correct	23 ms	852 KB	Output is correct
8	Correct	81 ms	1236 KB	Output is correct
9	Correct	187 ms	2132 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	80 ms	1364 KB	Output is correct
17	Correct	87 ms	1364 KB	Output is correct
18	Correct	21 ms	724 KB	Output is correct
19	Correct	82 ms	1236 KB	Output is correct
20	Correct	193 ms	2132 KB	Output is correct
21	Correct	1 ms	372 KB	Output is correct
22	Correct	1 ms	320 KB	Output is correct
23	Correct	1793 ms	8660 KB	Output is correct
24	Correct	1718 ms	8276 KB	Output is correct
25	Correct	207 ms	3156 KB	Output is correct
26	Correct	4120 ms	15572 KB	Output is correct
27	Correct	4128 ms	15444 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	7 ms	572 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	7 ms	572 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	7 ms	572 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	80 ms	1344 KB	Output is correct
6	Correct	89 ms	1352 KB	Output is correct
7	Correct	23 ms	852 KB	Output is correct
8	Correct	81 ms	1236 KB	Output is correct
9	Correct	187 ms	2132 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Incorrect	7 ms	572 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	7 ms	572 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	80 ms	1344 KB	Output is correct
6	Correct	89 ms	1352 KB	Output is correct
7	Correct	23 ms	852 KB	Output is correct
8	Correct	81 ms	1236 KB	Output is correct
9	Correct	187 ms	2132 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	80 ms	1364 KB	Output is correct
17	Correct	87 ms	1364 KB	Output is correct
18	Correct	21 ms	724 KB	Output is correct
19	Correct	82 ms	1236 KB	Output is correct
20	Correct	193 ms	2132 KB	Output is correct
21	Correct	1 ms	372 KB	Output is correct
22	Correct	1 ms	320 KB	Output is correct
23	Correct	1793 ms	8660 KB	Output is correct
24	Correct	1718 ms	8276 KB	Output is correct
25	Correct	207 ms	3156 KB	Output is correct
26	Correct	4120 ms	15572 KB	Output is correct
27	Correct	4128 ms	15444 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Incorrect	7 ms	572 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	7 ms	572 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	80 ms	1344 KB	Output is correct
6	Correct	89 ms	1352 KB	Output is correct
7	Correct	23 ms	852 KB	Output is correct
8	Correct	81 ms	1236 KB	Output is correct
9	Correct	187 ms	2132 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	80 ms	1364 KB	Output is correct
17	Correct	87 ms	1364 KB	Output is correct
18	Correct	21 ms	724 KB	Output is correct
19	Correct	82 ms	1236 KB	Output is correct
20	Correct	193 ms	2132 KB	Output is correct
21	Correct	1 ms	372 KB	Output is correct
22	Correct	1 ms	320 KB	Output is correct
23	Correct	1793 ms	8660 KB	Output is correct
24	Correct	1718 ms	8276 KB	Output is correct
25	Correct	207 ms	3156 KB	Output is correct
26	Correct	4120 ms	15572 KB	Output is correct
27	Correct	4128 ms	15444 KB	Output is correct
28	Correct	1 ms	596 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Incorrect	7 ms	572 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Submission #708405

Compilation message