Submission #867689

#	Time	Username	Problem	Language	Result	Execution time	Memory
867689		TAhmed33	Uplifting Excursion (BOI22_vault)	C++98	20 / 100	3295 ms	19284 KiB

vault

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll bad = -1e17;
const ll MAXN = 6e5;
ll dp[2 * MAXN], dq[2 * MAXN], n, l;
bool ok (ll x) {
    return x >= -MAXN && x < MAXN;
}
void chmax (ll &a, ll b) {
    a = max(a, b);
}
void insert (ll a, ll b) {
    for (ll i = -MAXN; i < MAXN; i++) {
        dq[i + MAXN] = dp[i + MAXN];
        if (ok(i - a * b)) chmax(dq[i + MAXN], b + dp[i - a * b + MAXN]);
    }
    if (ok(a * b)) chmax(dq[a * b + MAXN], b);
    for (ll i = -MAXN; i < MAXN; i++) dp[i + MAXN] = dq[i + MAXN];
}
int main () {
    cin >> n >> l;
    for (auto &i : dp) i = bad;
	for (ll i = -n; i <= n; i++) {
        int x;
        cin >> x;
        int u = 0;
        while ((1 << u) <= x) {
            insert(i, (1 << u));
            x -= (1 << u);
            u++;
        }
        if (x) insert(i, x);
    }
    if (!ok(l)) {
        cout << "impossible\n";
    } else if (dp[l + MAXN] < 0) {
        cout << "impossible\n";
    } else {
        cout << dp[l + MAXN] << '\n';
    }
}

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