Submission #910119

#TimeUsernameProblemLanguageResultExecution timeMemory
910119TigerpantsUplifting Excursion (BOI22_vault)C++17
100 / 100
954 ms3668 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rev_rep(i, a, b) for (ll i = a; i >= b; i--)
#define sz(a) (ll) a.size()
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define trav(itr, a, t) for (t::iterator itr = a.begin(); itr != a.end(); itr++)

const ll MAXM = 300LL;
const ll MAXB = MAXM * (2 * MAXM + 1LL);
const ll INF = 1'000'000'000'000'000'000LL;

ll M, L;
vll A;
vll in_greedy;

void reduce(vll& res, ll x, ll multiplier = 1) {
    res.clear();
    while (x) {
        res.pb(multiplier);
        x--;
        if (x & 1LL) {
            res.pb(multiplier);
            x--;
        }
        x >>= 1LL;
        multiplier *= 2LL;
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);

    cin >> M >> L;
    A.resize(2 * M + 1);
    rep(i, 0, 2 * M + 1) cin >> A[i];

    ll s = 0LL;
    rep(i, -M, M + 1) {
        s += A[i + M] * i;
    }
    if (s < L) { // reverse the problem
        rep(i, 1, M + 1) swap(A[M - i], A[M + i]);
        L *= -1;
    }

    // greedy
    in_greedy.resize(M + 1, 0);
    s = 0LL;
    ll n = 0LL;
    rep(i, -M, 1) {
        s += A[i + M] * i;
        n += A[i + M];
    }
    rep(i, 1, M + 1) {
        in_greedy[i] = max<ll>(0LL, min<ll>((L - s) / i, A[i + M]));
        s += in_greedy[i] * i;
        n += in_greedy[i];
    }

    // dp
    ll dp[2 * MAXB + 1];
    rep(i, 0, 2 * MAXB + 1) dp[i] = -INF;
    if ((L - s >= -MAXB) && (L - s <= MAXB)) dp[MAXB + (L - s)] = n; // base case

    vll deltas;

    rep(w, 1, M + 1) {
        // add w
        reduce(deltas, min<ll>(2 * M, A[w + M] - in_greedy[w]));
        trav(delta, deltas, vll) {
            rep(i, - MAXB, MAXB + 1 - (*delta) * w) {
                dp[i + MAXB] = max<ll>(dp[i + MAXB], dp[i + MAXB + (*delta) * w] + (*delta));
            }
        }

        // remove w
        reduce(deltas, min<ll>(2 * M, in_greedy[w]), -1);
        trav(delta, deltas, vll) {
            rev_rep(i, MAXB, - MAXB - (*delta) * w) {
                dp[i + MAXB] = max<ll>(dp[i + MAXB], dp[i + MAXB + (*delta) * w] + (*delta));
            }
        }
    }

    if (dp[MAXB] < 0) {
        cout << "impossible" << endl;
    } else {
        cout << dp[MAXB] << endl;
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...