Submission #1049854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049854		shiomusubi496	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	1677 ms	24184 KiB

vault

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

using namespace std;

constexpr ll inf = 1e18;

int main() {
    int M; cin >> M;
    ll L; cin >> L;
    vector<ll> A(2 * M + 1);
    rep (i, 2 * M + 1) cin >> A[i];
    if (L < 0) {
        reverse(all(A));
        L = -L;
    }
    ll sml = 0, smr = 0;
    rep (i, 2 * M + 1) {
        if (i < M) sml += A[i] * (i - M);
        if (i > M) smr += A[i] * (i - M);
    }
    if (L < sml || smr < L) {
        puts("impossible");
        return 0;
    }
    vector<pair<int, ll>> B;
    rep (i, 2 * M + 1) {
        if (i == M) continue;
        if (A[i] == 0) continue;
        // if (A[i] > M) continue;
        B.emplace_back(i - M, A[i]);
    }
    vector<ll> dp(smr - sml + 1, -inf);
    dp[0 - sml] = 0;
    for (auto [x, y] : B) {
        int ax = abs(x);
        vector<ll> memo;
        vector<ll> res;
        deque<int> st;
        rep (i, ax) {
            // mod x ごとにスライド最大値の形になる
            memo.clear();
            for (int j = i; j <= smr - sml; j += ax) {
                memo.push_back(dp[j]);
            }
            res.assign(memo.size(), -inf);
            st.clear();
            if (x > 0) {
                rep (i, memo.size()) memo[i] -= i;
                rep (i, res.size()) {
                    while (!st.empty() && st.front() < i - y) st.pop_front();
                    while (!st.empty() && memo[st.back()] < memo[i]) st.pop_back();
                    st.push_back(i);
                    res[i] = memo[st.front()] + i;
                }
            }
            else {
                rep (i, memo.size()) memo[i] += i;
                rrep (i, res.size()) {
                    while (!st.empty() && st.front() > i + y) st.pop_front();
                    while (!st.empty() && memo[st.back()] < memo[i]) st.pop_back();
                    st.push_back(i);
                    res[i] = memo[st.front()] - i;
                }
            }
            rep (j, res.size()) dp[j * ax + i] = res[j];
        }
    }
    if (dp[L - sml] >= 0) {
        cout << dp[L - sml] + A[M] << endl;
    }
    else {
        puts("impossible");
    }
}

• 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