Submission #908591

#	Time	Username	Problem	Language	Result	Execution time	Memory
908591		Tigerpants	Uplifting Excursion (BOI22_vault)	C++17	50 / 100	1033 ms	524288 KiB

vault

#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 = 2 * MAXM * (MAXM + 1LL);
const ll INF = 1'000'000'000'000'000'000LL;

ll M, L;
vll A;
vll in_greedy;

vll reduce(ll x, ll multiplier = 1) {
    vll res;
    while (x) {
        //cout << "reduce " << x << " " << multiplier << endl;
        res.pb(multiplier);
        x--;
        if (x & 1) {
            res.pb(multiplier);
            x--;
        }
        x >>= 1;
        multiplier *= 2;
    }
    return res;
}

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
        //cout << "reverse " << s << endl;
        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];
    }
    //cout << L << " " << s << " " << n << endl;
    rep(i, 1, M + 1) {
        in_greedy[i] = min<ll>((L - s) / i, A[i + M]);
        //cout << i << " -> " << in_greedy[i] << endl;
        s += in_greedy[i] * i;
        n += in_greedy[i];
    }
    //cout << "n=" << n << endl;

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

    /* rep(i, -10, 11) {
        cout << dp[i + MAXB] << " ";
    }
    cout << endl; */

    rep(w, 1, M + 1) {
        // add w
        vll deltas = reduce(min<ll>(2 * M, A[w + M] - in_greedy[w]));
        /* cout << min<ll>(2 * M, A[w + M] - in_greedy[w]) << " -> {";
        trav(delta, deltas, vll) cout << (*delta) << " ";
        cout << "}" << endl; */
        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
        deltas = reduce(min<ll>(2 * M, in_greedy[w]), -1);
        /* cout << min<ll>(2 * M, in_greedy[w]) << " -> {";
        trav(delta, deltas, vll) cout << (*delta) << " ";
        cout << "}" << endl; */
        trav(delta, deltas, vll) {
            rev_rep(i, MAXB, - MAXB - (*delta) * w) {
                //cout << (*delta) << " " << i + MAXB - (*delta) << " " << 2 * MAXB << endl;
                dp[i + MAXB] = max<ll>(dp[i + MAXB], dp[i + MAXB + (*delta) * w] + (*delta));
            }
        }

        /* rep(i, -10, 11) {
            cout << dp[i + MAXB] << " ";
        }
        cout << endl; */
    }

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

    return 0;
}

// the dp covers the range of uplifts [L - M - 2M^2, L + M + 2M^2]
// in each step, we consider adding up to min<ll>(2 * M, A[w + M] - in_greedy[w]) of weight w, or removng up to min<ll>(2 * M, in_greedy[w])

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