Submission #588778

#	Time	Username	Problem	Language	Result	Execution time	Memory
588778		maomao90	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	754 ms	2464 KiB

vault

#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int MAXN = 305;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MOD = 1000000007;

int m;
ll l;
ll a[MAXN * 2];
ll ans;

struct item {
    int v;
    ll a;
    int c;
};
vector<item> items;

ll getitems() {
    ll tot = 0;
    REP (i, -m, m + 1) {
        if (i <= 0) {
            tot += a[i + MAXN] * i;
            ans += a[i + MAXN];
            if (i != 0) {
                items.pb({-i, a[i + MAXN], -1});
            }
        } else {
            ll dif = l - tot;
            ll take = min(a[i + MAXN], dif / i);
            tot += take * i;
            ans += take;
            if (take > 0) {
                items.pb({-i, take, -1});
            }
            if (a[i + MAXN] - take > 0) {
                items.pb({i, a[i + MAXN] - take, 1});
            }
        }
    }
    return tot;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> m >> l;
    REP (i, -m, m + 1) {
        cin >> a[i + MAXN];
    }
    if (l < 0) {
        l *= -1;
        reverse(a + MAXN - m, a + MAXN + m + 1);
    }
    ll tot = 0;
    REP (i, 1, m + 1) {
        tot += a[i + MAXN] * i;
    }
    if (tot < l) {
        cout << "impossible\n";
        return 0;
    }
    tot = getitems();
    ll rem = l - tot;
    if (rem > m) {
        l *= -1;
        reverse(a + MAXN - m, a + MAXN + m + 1);
        ans = 0;
        items.clear();
        tot = getitems();
        rem = l - tot;
    }
    cerr << ans << ' ' << tot << '\n';
    assert(rem <= m);
    int sz = m * m;
    vll dp(sz * 2 + 5, -LINF);
    dp[sz] = 0;
    for (auto [v, a, c] : items) {
        for (ll k = 0; abs(k) < abs(v); k += v / abs(v)) {
            int ptr = 0;
            deque<pll> dq;
            for (ll j = (v < 0 ? sz : -sz) + k; j <= sz && j >= -sz; j += v) {
                while (!dq.empty() && ptr - dq.front().SE > a) {
                    dq.pop_front();
                }
                if (dp[j + sz] != -LINF) {
                    while (!dq.empty() && dq.back().FI - dq.back().SE * c <= 
                            dp[j + sz] - ptr * c) {
                        dq.pop_back();
                    }
                    dq.pb({dp[j + sz], ptr});
                }
                if (dq.empty()) {
                    dp[j + sz] = -LINF;
                } else {
                    dp[j + sz] = dq.front().FI + ptr * c - dq.front().SE * c;
                }
                ptr++;
                cerr << j << ' ' << dp[j + sz] << '\n';
            }
        }
    }
    if (dp[rem + sz] == -LINF) {
        cout << "impossible\n";
    } else {
        cout << ans + dp[rem + sz] << '\n';
    }
    return 0;
}

• 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