Submission #625243

#	Time	Username	Problem	Language	Result	Execution time	Memory
625243		Ooops_sorry	Uplifting Excursion (BOI22_vault)	C++14	100 / 100	2766 ms	4788 KiB

vault

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll long long

mt19937 rnd(51);

const int INF = 1e9, M = 5.1e5 + 10, N = 1e3 + 10;

vector<int> calc_dp(vector<pair<int, ll>> u, bool f, int n) {
    vector<int> dp(n);
    vector<pair<ll, ll>> upd;
    for (int i = 0; i < u.size(); i++) {
        ll t = 0;
        while ((1LL << (t + 1)) <= u[i].second) {
            t++;
        }
        for (int j = 0; j < t; j++) {
            upd.pb({u[i].first * (1LL << j), (1LL << j)});
        }
        upd.pb({u[i].first * (u[i].second - (1LL << t) + 1), (u[i].second - (1LL << t) + 1)});
    }
    if (f) {
        for (int i = 1; i < n; i++) dp[i] = -INF;
    } else {
        for (int i = 1; i < n; i++) dp[i] = INF;
    }
    for (auto to : upd) {
        if (to.first >= n) continue;
        if (f) {
            for (int j = n - to.first - 1; j >= 0; j--) {
                if (dp[j] != -INF) {
                    dp[j + to.first] = max(dp[j + to.first], dp[j] + (int)to.second);
                }
            }
        } else {
            for (int j = n - to.first - 1; j >= 0; j--) {
                if (dp[j] != INF) {
                    dp[j + to.first] = min(dp[j + to.first], dp[j] + (int)to.second);
                }
            }
        }
    }
    return dp;
}

ll solve_pos(ll m, ll L, vector<ll> pos, int need_const) {
    if (L < 0) {
        return -1;
    }
    ll sum = L, cnt = 0;
    vector<pair<int, ll>> u1, u2;
    for (ll i = 1; i <= m; i++) {
        if (i * pos[i] > sum) {
            ll can = sum / i;
            sum -= can * i;
            cnt += can;
            u1.pb({i, can});
            u2.pb({i, pos[i] - can});
            for (int j = i + 1; j <= m; j++) {
                u2.pb({j, pos[j]});
            }
            break;
        } else {
            sum -= i * pos[i];
            cnt += pos[i];
            u1.pb({i, pos[i]});
        }
    }
    if (sum == 0) {
        return cnt;
    } else {
        vector<int> dp1 = calc_dp(u1, 0, need_const), dp2 = calc_dp(u2, 1, need_const);
        ll mx = -1;
        for (int j = 0; j + sum < need_const; j++) {
            if (dp2[j + sum] >= 0 && dp1[j] != INF) {
                mx = max(mx, cnt + dp2[j + sum] - dp1[j]);
            }
        }
        return mx;
    }
}

ll solve_any(ll m, ll L, vector<ll> neg, vector<ll> pos) {
    ll sum_neg = 0, sum_pos = 0;
    vector<pair<int, ll>> u1, u2;
    for (int i = 1; i <= m; i++) {
        u1.pb({i, neg[i]});
        sum_neg += i * neg[i];
    }
    for (int i = 1; i <= m; i++) {
        u2.pb({i, pos[i]});
        sum_pos += i * pos[i];
    }
    if (L > sum_pos) return -1;
    vector<int> dp1 = calc_dp(u1, 1, M), dp2 = calc_dp(u2, 1, M);
    ll mx = -1;
    ll need_val = min(sum_neg, sum_pos - L);
    for (int j = -100; j <= 100; j++) {
        ll res = solve_pos(m, j + need_val, neg, N);
        ll res2 = solve_pos(m, L + (j + need_val), pos, N);
        if (res != -1 && res2 != -1) {
            mx = max(mx, res + res2);
        }
    }
    return mx;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll m, L;
    cin >> m >> L;
    ll zero = 0;
    vector<ll> neg, pos{0};
    for (int i = 0; i < 2 * m + 1; i++) {
        ll a;
        cin >> a;
        if (i < m) {
            neg.pb(a);
        } else if (i == m) {
            zero += a;
        } else {
            pos.pb(a);
        }
    }
    neg.pb(0);
    reverse(neg.begin(), neg.end());
    ll mx = 0;
    for (auto to : neg) {
        mx = max(mx, to);
    }
    ll res;
    if (mx == 0) {
        res = solve_pos(m, L, pos, M);
    } else {
        if (L < 0) {
            L = abs(L);
            swap(neg, pos);
        }
        res = solve_any(m, L, neg, pos);
    }
    if (res == -1) {
        cout << "impossible" << endl;
    } else {
        cout << zero + res << endl;
    }
    return 0;
}

Compilation message (stderr)

vault.cpp: In function 'std::vector<int> calc_dp(std::vector<std::pair<int, long long int> >, bool, int)':
vault.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

• 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