oj.uz

Submission #599328

# Submission time Handle Problem Language Result Execution time Memory
599328 2022-07-19T12:42:57 Z alextodoran Uplifting Excursion (BOI22_vault) C++17
0 / 100
 0 ms 340 KB 
/**
 ____ ____ ____ ____ ____
||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, Sl, Sr;
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 - Sl, maxTakeBit + Sr + 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 = -Sl - l; s <= +Sr; 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 = +Sl - l; s >= -Sr; 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);
    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);
        }
    }
    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;
        }
        Sr = max(Sr, mx);
        Sl = max(Sl, -mn);
    }

    solveBit(0);
    for (int here = -Sl; here <= +Sr; 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 = -Sl; carry <= +Sr; carry++) {
            if (maxTake[bit - 1][carry] != -INF) {
                carries.push_back(carry);
            }
        }
        for (int here = -Sl; here <= +Sr; 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.0

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

Subtask #2
0 / 15.0

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

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 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 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 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 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 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 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -