Submission #1049834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049834		shiomusubi496	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5045 ms	12360 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);
        rep (i, ax) {
            // mod x ごとにスライド最大値の形になる
            vector<ll> memo;
            for (int j = i; j <= smr - sml; j += ax) {
                memo.push_back(dp[j]);
            }
            vector<ll> res(memo.size(), -inf);
            if (x > 0) {
                rep (i, res.size()) {
                    rep (j, y + 1) {
                        if (i - j >= 0) chmax(res[i], memo[i - j] + j);
                        else break;
                    }
                }
            }
            else {
                rep (i, res.size()) {
                    rep (j, y + 1) {
                        if (i + j < res.size()) chmax(res[i], memo[i + j] + j);
                        else break;
                    }
                }
            }
            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");
    }
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:68:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                         if (i + j < res.size()) chmax(res[i], memo[i + j] + j);
      |                             ~~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 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