oj.uz

Submission #949631

# Submission time Handle Problem Language Result Execution time Memory
949631 2024-03-19T13:14:24 Z ifateen Uplifting Excursion (BOI22_vault) C++17
5 / 100
 2466 ms 8284 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int OFFSET, OFFSET_SUM;
int dp[2][250'005];

signed main() {
    int n, l;
    cin >> n >> l;
    vector<int> v(2 * n + 1);
    for (auto& i : v) cin >> i;
    OFFSET = n, OFFSET_SUM = n * 50 * 50;
    if (l > OFFSET_SUM || l < -OFFSET_SUM) {
        cout << "impossible";
        return 0;
    }
    for (int i = 0; i <= 2 * OFFSET_SUM; ++i) dp[0][i] = dp[1][i] = -1e9;
    dp[1][OFFSET_SUM] = 0;
    for (int i = 0; i <= 2 * n; ++i) {
        int actual_value = i - OFFSET;
        for (int j = 0; j <= OFFSET_SUM * 2; ++j) {
            dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][j]);
            for (int k = 1; k <= v[i]; ++k) {
                int prv_sum = j - k * actual_value;
                if (prv_sum < 0 || prv_sum > OFFSET_SUM * 2) continue;
                dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][prv_sum] + k);
            }
        }
    }
    int ans = dp[0][OFFSET_SUM + l];
    if (ans <= 0) cout << "impossible";
    else cout << ans;
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:22:51: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   22 |             dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][j]);
      |                                                 ~~^~~
vault.cpp:26:55: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |                 dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1 ^ 1][prv_sum] + k);
      |                                                     ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1362 ms 4324 KB Output is correct
7 Correct 476 ms 4324 KB Output is correct
8 Correct 1433 ms 4332 KB Output is correct
9 Correct 2382 ms 4328 KB Output is correct
10 Correct 65 ms 4328 KB Output is correct
11 Correct 46 ms 4328 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1362 ms 4324 KB Output is correct
7 Correct 476 ms 4324 KB Output is correct
8 Correct 1433 ms 4332 KB Output is correct
9 Correct 2382 ms 4328 KB Output is correct
10 Correct 65 ms 4328 KB Output is correct
11 Correct 46 ms 4328 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 5 ms 2652 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 866 ms 4324 KB Output is correct
18 Correct 407 ms 4432 KB Output is correct
19 Correct 1211 ms 4324 KB Output is correct
20 Correct 2466 ms 4324 KB Output is correct
21 Correct 71 ms 4188 KB Output is correct
22 Correct 53 ms 4188 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Runtime error 5 ms 8284 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1362 ms 4324 KB Output is correct
7 Correct 476 ms 4324 KB Output is correct
8 Correct 1433 ms 4332 KB Output is correct
9 Correct 2382 ms 4328 KB Output is correct
10 Correct 65 ms 4328 KB Output is correct
11 Correct 46 ms 4328 KB Output is correct
12 Correct 5 ms 2648 KB Output is correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1362 ms 4324 KB Output is correct
7 Correct 476 ms 4324 KB Output is correct
8 Correct 1433 ms 4332 KB Output is correct
9 Correct 2382 ms 4328 KB Output is correct
10 Correct 65 ms 4328 KB Output is correct
11 Correct 46 ms 4328 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 5 ms 2652 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 866 ms 4324 KB Output is correct
18 Correct 407 ms 4432 KB Output is correct
19 Correct 1211 ms 4324 KB Output is correct
20 Correct 2466 ms 4324 KB Output is correct
21 Correct 71 ms 4188 KB Output is correct
22 Correct 53 ms 4188 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Runtime error 5 ms 8284 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1362 ms 4324 KB Output is correct
7 Correct 476 ms 4324 KB Output is correct
8 Correct 1433 ms 4332 KB Output is correct
9 Correct 2382 ms 4328 KB Output is correct
10 Correct 65 ms 4328 KB Output is correct
11 Correct 46 ms 4328 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 5 ms 2652 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 866 ms 4324 KB Output is correct
18 Correct 407 ms 4432 KB Output is correct
19 Correct 1211 ms 4324 KB Output is correct
20 Correct 2466 ms 4324 KB Output is correct
21 Correct 71 ms 4188 KB Output is correct
22 Correct 53 ms 4188 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Runtime error 5 ms 8284 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -