Submission #599321

#	Time	Username	Problem	Language	Result	Execution time	Memory
599321		alextodoran	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	596 KiB

vault

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const int BITS = 56;
const ll INF = LLONG_MAX / 2;

int M;
ll L;
int* A[BITS];

int S;
ll* maxTake[BITS];
ll* maxTakeBit;

void init () {
    for (int bit = 0; bit < BITS; bit++) {
        A[bit] = new int[M * 2 + 1] + M;
        maxTake[bit] = new ll[S * 2 + 1] + S;
        fill(A[bit] - M, A[bit] + M + 1, 0);
        fill(maxTake[bit] - S, maxTake[bit] + S + 1, -INF);
    }
    maxTakeBit = new ll[S * 2 + 1] + S;
}

void solveBit (int bit) {
    fill(maxTakeBit - S, maxTakeBit + S + 1, -INF);
    maxTakeBit[0] = 0;
    for (int l = -M; l <= M; l++) {
        if (l < 0) {
            for (int i = 1; i <= A[bit][l]; i++) {
                for (int s = -S - l; s <= +S; s++) {
                    if (maxTakeBit[s] != -INF) {
                        maxTakeBit[s + l] = max(maxTakeBit[s + l], maxTakeBit[s] + 1);
                    }
                }
            }
        } else {
            for (int i = 1; i <= A[bit][l]; i++) {
                for (int s = +S - l; s >= -S; s--) {
                    if (maxTakeBit[s] != -INF) {
                        maxTakeBit[s + l] = max(maxTakeBit[s + l], maxTakeBit[s] + 1);
                    }
                }
            }
        }
    }
}

void update (ll &x, const ll &y) {
    if (y > x) {
        x = y;
    }
}

mt19937_64 rnd(0);

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

    cin >> M >> L;
    S = M * (M + 1) / 2;
    init();
    ll sumNeg = 0, sumPos = 0;
    for (int l = -M; l <= +M; l++) {
        ll cnt; cin >> cnt;
        if (l > 0) {
            sumPos += cnt * l;
        } else {
            sumNeg += cnt * l;
        }
        int bit = 0;
        while (((ll) 1 << bit) <= cnt) {
            cnt -= ((ll) 1 << bit);
            A[bit][l]++;
            bit++;
        }
        for (int bit = 0; bit < BITS; bit++) {
            if ((cnt >> bit) & 1) {
                A[bit][l]++;
            }
        }
    }
    if (L < sumNeg || sumPos < L) {
        cout << "impossible\n";
        return 0;
    }
    if (L < 0) {
        L = -L;
        for (int bit = 0; bit < BITS; bit++) {
            reverse(A[bit] - M, A[bit] + M + 1);
        }
    }
    S = 0;
    for (int bit = 0; bit < BITS; bit++) {
        int mx = 0, mn = 0;
        for (int l = +1; l <= +M; l++) {
            mx += A[bit][l] * l;
        }
        for (int l = -1; l >= -M; l--) {
            mn += A[bit][l] * l;
        }
        S = max(S, mx);
        S = max(S, -mn);
    }

    solveBit(0);
    for (int here = -S; here <= +S; here++) {
        int sum = here - (L & 1);
        if ((sum & 1) == 0) {
            update(maxTake[0][sum >> 1], maxTakeBit[here]);
        }
    }
    for (int bit = 1; bit < BITS; bit++) {
        solveBit(bit);
        vector <int> carries;
        for (int carry = -S; carry <= +S; carry++) {
            if (maxTake[bit - 1][carry] != -INF) {
                carries.push_back(carry);
            }
        }
        for (int here = -S; here <= +S; here++) {
            if (maxTakeBit[here] != -INF) {
                for (int carry : carries) {
                    int sum = carry + here - ((L >> bit) & 1);
                    if ((sum & 1) == 0) {
                        update(maxTake[bit][sum >> 1], maxTake[bit - 1][carry] + (maxTakeBit[here] << bit));
                    }
                }
            }
        }
    }
    ll answer = maxTake[BITS - 1][0];
    if (answer != -INF) {
        cout << answer << "\n";
    } else {
        cout << "impossible\n";
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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