Submission #582856

#	Time	Username	Problem	Language	Result	Execution time	Memory
582856		KoD	Uplifting Excursion (BOI22_vault)	C++17	40 / 100	2221 ms	1276 KiB

vault

#include <bits/stdc++.h>

using ll = long long;

using std::vector;
using std::pair;
using std::deque;

constexpr int inf = std::numeric_limits<int>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int M;
    ll T;
    std::cin >> M >> T;
    vector<ll> A(2 * M + 1);
    ll S = 0;
    for (int i = -M; i <= M; ++i) {
        std::cin >> A[i + M];
        S += i * A[i + M];
    }
    if (S < 0) {
        T = -T;
        std::reverse(A.begin(), A.end());
    }
    const int N = M * M;
    vector<int> dp(2 * N + 1, -inf);
    dp[N] = 0;
    const auto update_positive = [&](const ll K, const int W, const int V) {
        for (int r = 0; r < W; ++r) {
            if (r >= (int)dp.size()) {
                break;
            }
            deque<pair<int, int>> deq;
            for (int q = 0;; ++q) {
                const int i = q * W + r;
                if (i >= (int)dp.size()) {
                    break;
                }
                const int add = dp[i] - q * V;
                while (!deq.empty() and deq.back().first < add) {
                    deq.pop_back();
                }
                deq.emplace_back(add, q);
                while (deq.front().second + K < q) {
                    deq.pop_front();
                }
                dp[i] = deq.front().first + q * V;
            }
        }
    };
    const auto update = [&](const ll K, const int W, const int V) {
        if (W > 0) {
            update_positive(K, W, V);
        }
        if (W < 0) {
            std::reverse(dp.begin(), dp.end());
            update_positive(K, -W, V);
            std::reverse(dp.begin(), dp.end());
        }
    };
    S = 0;
    ll sum = 0;
    for (int i = -M; i <= M; ++i) {
        const ll take = i <= 0 ? A[i + M] : std::min(A[i + M], (T - S) / i);
        const ll remain = A[i + M] - take;
        S += i * take;
        sum += take;
        update(take, -i, -1);
        update(remain, i, 1);
    }
    if (std::abs(T - S) > N or dp[T - S + N] < -2 * M) {
        std::cout << "impossible\n";
    } else {
        std::cout << sum + dp[T - S + N] << '\n'; 
    }
    return 0;
}

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