oj.uz

Submission #604343

# Submission time Handle Problem Language Result Execution time Memory
604343 2022-07-25T04:24:12 Z Jomnoi Uplifting Excursion (BOI22_vault) C++17
5 / 100
 3080 ms 4512 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;
const int MAX_W = 130005;
const int INF = 1e9 + 7;

long long A[MAX_N], dp[2][MAX_W];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int M;
    long long L;
    cin >> M >> L;

    for(int i = -M; i <= M; i++) {
        cin >> A[i + M];
    }

    for(int i = 0; i < MAX_W; i++) {
        dp[0][i] = -INF;
    }
    dp[0][MAX_W / 2] = 0;

    int j = 1;
    for(int i = -M; i <= M; i++, j ^= 1) {
        int now = j, pre = j ^ 1;
        for(int j = MAX_W - 1; j >= 0; j--) {
            dp[now][j] = dp[pre][j];
            for(int k = 0; k <= A[i + M]; k++) {
                if(j - k * i >= 0 and j - k * i < MAX_W and dp[pre][j - k * i] != -INF) {
                    dp[now][j] = max(dp[now][j], dp[pre][j - k * i] + k);
                }
            }
        }
    }

    if(abs(L) > MAX_W / 2 or dp[j ^ 1][MAX_W / 2 + L] == -INF) {
        cout << "impossible";
    }
    else {
        cout << dp[j ^ 1][MAX_W / 2 + L];
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 12 ms 2348 KB Output is correct
5 Correct 481 ms 2332 KB Output is correct
6 Correct 504 ms 2332 KB Output is correct
7 Correct 178 ms 2332 KB Output is correct
8 Correct 469 ms 2340 KB Output is correct
9 Correct 1158 ms 2332 KB Output is correct
10 Correct 34 ms 2260 KB Output is correct
11 Correct 31 ms 2336 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 12 ms 2348 KB Output is correct
5 Correct 481 ms 2332 KB Output is correct
6 Correct 504 ms 2332 KB Output is correct
7 Correct 178 ms 2332 KB Output is correct
8 Correct 469 ms 2340 KB Output is correct
9 Correct 1158 ms 2332 KB Output is correct
10 Correct 34 ms 2260 KB Output is correct
11 Correct 31 ms 2336 KB Output is correct
12 Correct 4 ms 2260 KB Output is correct
13 Correct 3 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2352 KB Output is correct
16 Correct 492 ms 2332 KB Output is correct
17 Correct 521 ms 2332 KB Output is correct
18 Correct 222 ms 2260 KB Output is correct
19 Correct 529 ms 2332 KB Output is correct
20 Correct 1268 ms 2336 KB Output is correct
21 Correct 32 ms 2260 KB Output is correct
22 Correct 39 ms 2332 KB Output is correct
23 Runtime error 3080 ms 4504 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2356 KB Output is correct
2 Runtime error 1061 ms 4512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2356 KB Output is correct
2 Runtime error 1061 ms 4512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2356 KB Output is correct
2 Runtime error 1061 ms 4512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 12 ms 2348 KB Output is correct
5 Correct 481 ms 2332 KB Output is correct
6 Correct 504 ms 2332 KB Output is correct
7 Correct 178 ms 2332 KB Output is correct
8 Correct 469 ms 2340 KB Output is correct
9 Correct 1158 ms 2332 KB Output is correct
10 Correct 34 ms 2260 KB Output is correct
11 Correct 31 ms 2336 KB Output is correct
12 Correct 18 ms 2356 KB Output is correct
13 Runtime error 1061 ms 4512 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2356 KB Output is correct
2 Runtime error 1061 ms 4512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 12 ms 2348 KB Output is correct
5 Correct 481 ms 2332 KB Output is correct
6 Correct 504 ms 2332 KB Output is correct
7 Correct 178 ms 2332 KB Output is correct
8 Correct 469 ms 2340 KB Output is correct
9 Correct 1158 ms 2332 KB Output is correct
10 Correct 34 ms 2260 KB Output is correct
11 Correct 31 ms 2336 KB Output is correct
12 Correct 4 ms 2260 KB Output is correct
13 Correct 3 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2352 KB Output is correct
16 Correct 492 ms 2332 KB Output is correct
17 Correct 521 ms 2332 KB Output is correct
18 Correct 222 ms 2260 KB Output is correct
19 Correct 529 ms 2332 KB Output is correct
20 Correct 1268 ms 2336 KB Output is correct
21 Correct 32 ms 2260 KB Output is correct
22 Correct 39 ms 2332 KB Output is correct
23 Runtime error 3080 ms 4504 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2356 KB Output is correct
2 Runtime error 1061 ms 4512 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 12 ms 2348 KB Output is correct
5 Correct 481 ms 2332 KB Output is correct
6 Correct 504 ms 2332 KB Output is correct
7 Correct 178 ms 2332 KB Output is correct
8 Correct 469 ms 2340 KB Output is correct
9 Correct 1158 ms 2332 KB Output is correct
10 Correct 34 ms 2260 KB Output is correct
11 Correct 31 ms 2336 KB Output is correct
12 Correct 4 ms 2260 KB Output is correct
13 Correct 3 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2352 KB Output is correct
16 Correct 492 ms 2332 KB Output is correct
17 Correct 521 ms 2332 KB Output is correct
18 Correct 222 ms 2260 KB Output is correct
19 Correct 529 ms 2332 KB Output is correct
20 Correct 1268 ms 2336 KB Output is correct
21 Correct 32 ms 2260 KB Output is correct
22 Correct 39 ms 2332 KB Output is correct
23 Runtime error 3080 ms 4504 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -