Submission #1172517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172517		Iskachun	Uplifting Excursion (BOI22_vault)	C++20	100 / 100	1752 ms	3512 KiB

vault

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
void solve () {
    ll m, l; cin >> m >> l;
    ll n = 2 * m + 1;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    ll sum = 0;
    vector<ll> c(n);
    for (ll i = 0; i <= m; i++) sum += (i - m) * a[i], c[i] = a[i];
    for (ll i = m + 1; i < n; i++) {
        c[i] = min(a[i], (l - sum) / (i - m));
        sum += c[i] * (i - m);
    }
    for (ll i = 0; i < m; i++) {
        ll val = min(a[i], (l - sum) / (m - i));
        c[i] -= val;
        sum += val * (m - i);
    }
    if (abs(sum - l) > m) return cout << "impossible", void();
    vector<pair<ll, ll>> cnt;
    ll tot = 0;
    for (ll i = 0; i < n; i++) {
        tot += c[i];
        if (i == m) continue;
        ll j = 1, s = min(m * m, a[i] - c[i]);
        while (j <= s) {
            cnt.push_back({j * (i - m), j});
            s -= j, j *= 2;
        }
        if (s > 0) cnt.push_back({s * (i - m), s});
        j = 1, s = min(c[i], m * m);
        while (j <= s) {
            cnt.push_back({j * (m - i), -j});
            s -= j, j *= 2;
        }
        if (s > 0) cnt.push_back({s * (m - i), -s});
    }
    ll m2 = m * m;
    vector<ll> dp(2 * m2 + 10, -1e18), f(2 * m2 + 10, -1e18);
    dp[m2] = f[m2] = 0;
    for (auto [x, y] : cnt) {
        for (ll i = 0; i <= 2 * m2; i++) {
            if (i - x <= 2 * m2 and i - x >= 0 and dp[i - x] != -1e18) f[i] = max(f[i], dp[i - x] + y);
        }
        dp = f;
    }
    if (f[l - sum + m2] + tot >= 0) cout << f[l - sum + m2] + tot;
    else cout << "impossible";
}
int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();

}

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