oj.uz

Submission #1049834

# Submission time Handle Problem Language Result Execution time Memory
1049834 2024-08-09T05:40:11 Z shiomusubi496 Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 12360 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 207 ms 2540 KB Output is correct
7 Correct 35 ms 776 KB Output is correct
8 Correct 204 ms 1904 KB Output is correct
9 Correct 560 ms 3212 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 207 ms 2540 KB Output is correct
7 Correct 35 ms 776 KB Output is correct
8 Correct 204 ms 1904 KB Output is correct
9 Correct 560 ms 3212 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 200 ms 2440 KB Output is correct
18 Correct 37 ms 856 KB Output is correct
19 Correct 193 ms 1916 KB Output is correct
20 Correct 544 ms 3336 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 4810 ms 12360 KB Output is correct
25 Correct 731 ms 2464 KB Output is correct
26 Execution timed out 5045 ms 8584 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 207 ms 2540 KB Output is correct
7 Correct 35 ms 776 KB Output is correct
8 Correct 204 ms 1904 KB Output is correct
9 Correct 560 ms 3212 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 207 ms 2540 KB Output is correct
7 Correct 35 ms 776 KB Output is correct
8 Correct 204 ms 1904 KB Output is correct
9 Correct 560 ms 3212 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 200 ms 2440 KB Output is correct
18 Correct 37 ms 856 KB Output is correct
19 Correct 193 ms 1916 KB Output is correct
20 Correct 544 ms 3336 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 4810 ms 12360 KB Output is correct
25 Correct 731 ms 2464 KB Output is correct
26 Execution timed out 5045 ms 8584 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 207 ms 2540 KB Output is correct
7 Correct 35 ms 776 KB Output is correct
8 Correct 204 ms 1904 KB Output is correct
9 Correct 560 ms 3212 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 200 ms 2440 KB Output is correct
18 Correct 37 ms 856 KB Output is correct
19 Correct 193 ms 1916 KB Output is correct
20 Correct 544 ms 3336 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 4810 ms 12360 KB Output is correct
25 Correct 731 ms 2464 KB Output is correct
26 Execution timed out 5045 ms 8584 KB Time limit exceeded
27 Halted 0 ms 0 KB -