oj.uz

Submission #937876

# Submission time Handle Problem Language Result Execution time Memory
937876 2024-03-04T15:54:02 Z LucaIlie Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 19556 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX_M = 300;
const int MAX_S = 6e5;
const int MIN_S = -MAX_S;
const long long INF = 1e18;
long long a[2 * MAX_M + 1];
long long maxObj[MAX_S - MIN_S + 1];

signed main() {
    int m, l;

    cin >> m >> l;
    for ( int i = 0; i <= 2 * m; i++ )
        cin >> a[i];

    for ( int s = 0; s <= MAX_S - MIN_S; s++ )
        maxObj[s] = -INF;
    maxObj[0 - MIN_S] = 0;
    for ( int i = 0; i <= 2 * m; i++ ) {
        long long y = i - m, s = 0;
        for ( int j = 1; s + j <= a[i]; s += j, j++ ) {
            long long x = y * j;
            if ( x > 0 ) {
                for ( int s = MAX_S - MIN_S; s >= x; s-- )
                    maxObj[s] = max( maxObj[s], maxObj[s - x] + j );
            } else {
                for ( int s = x; s <= MAX_S - MIN_S; s++ )
                    maxObj[s] = max( maxObj[s], maxObj[s - x] + j );
            }
        }
        for ( ; s + 1 <= a[i]; s++ ) {
            long long x = y;
            if ( x > 0 ) {
                for ( int s = MAX_S - MIN_S; s >= x; s-- )
                    maxObj[s] = max( maxObj[s], maxObj[s - x] + 1 );
            } else {
                for ( int s = x; s <= MAX_S - MIN_S; s++ )
                    maxObj[s] = max( maxObj[s], maxObj[s - x] + 1 );
            }
        }
    }

    if ( l < MIN_S || l > MAX_S || maxObj[l - MIN_S] < 0 )
        cout << "impossible\n";
    else
        cout << maxObj[l - MIN_S] << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9816 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 33 ms 9820 KB Output is correct
5 Correct 762 ms 9820 KB Output is correct
6 Correct 801 ms 9816 KB Output is correct
7 Correct 309 ms 9816 KB Output is correct
8 Correct 779 ms 9820 KB Output is correct
9 Correct 1016 ms 9816 KB Output is correct
10 Correct 29 ms 9816 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9816 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 33 ms 9820 KB Output is correct
5 Correct 762 ms 9820 KB Output is correct
6 Correct 801 ms 9816 KB Output is correct
7 Correct 309 ms 9816 KB Output is correct
8 Correct 779 ms 9820 KB Output is correct
9 Correct 1016 ms 9816 KB Output is correct
10 Correct 29 ms 9816 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 10 ms 9816 KB Output is correct
13 Correct 9 ms 9816 KB Output is correct
14 Correct 5 ms 9816 KB Output is correct
15 Correct 33 ms 9832 KB Output is correct
16 Correct 760 ms 9824 KB Output is correct
17 Correct 768 ms 9816 KB Output is correct
18 Correct 309 ms 9820 KB Output is correct
19 Correct 819 ms 9816 KB Output is correct
20 Correct 1018 ms 9820 KB Output is correct
21 Correct 36 ms 9816 KB Output is correct
22 Correct 33 ms 9816 KB Output is correct
23 Correct 2298 ms 9820 KB Output is correct
24 Runtime error 21 ms 19556 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 33 ms 9816 KB Output is correct
2 Execution timed out 5067 ms 9820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9816 KB Output is correct
2 Execution timed out 5067 ms 9820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9816 KB Output is correct
2 Execution timed out 5067 ms 9820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9816 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 33 ms 9820 KB Output is correct
5 Correct 762 ms 9820 KB Output is correct
6 Correct 801 ms 9816 KB Output is correct
7 Correct 309 ms 9816 KB Output is correct
8 Correct 779 ms 9820 KB Output is correct
9 Correct 1016 ms 9816 KB Output is correct
10 Correct 29 ms 9816 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 33 ms 9816 KB Output is correct
13 Execution timed out 5067 ms 9820 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9816 KB Output is correct
2 Execution timed out 5067 ms 9820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9816 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 33 ms 9820 KB Output is correct
5 Correct 762 ms 9820 KB Output is correct
6 Correct 801 ms 9816 KB Output is correct
7 Correct 309 ms 9816 KB Output is correct
8 Correct 779 ms 9820 KB Output is correct
9 Correct 1016 ms 9816 KB Output is correct
10 Correct 29 ms 9816 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 10 ms 9816 KB Output is correct
13 Correct 9 ms 9816 KB Output is correct
14 Correct 5 ms 9816 KB Output is correct
15 Correct 33 ms 9832 KB Output is correct
16 Correct 760 ms 9824 KB Output is correct
17 Correct 768 ms 9816 KB Output is correct
18 Correct 309 ms 9820 KB Output is correct
19 Correct 819 ms 9816 KB Output is correct
20 Correct 1018 ms 9820 KB Output is correct
21 Correct 36 ms 9816 KB Output is correct
22 Correct 33 ms 9816 KB Output is correct
23 Correct 2298 ms 9820 KB Output is correct
24 Runtime error 21 ms 19556 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 33 ms 9816 KB Output is correct
2 Execution timed out 5067 ms 9820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9816 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 33 ms 9820 KB Output is correct
5 Correct 762 ms 9820 KB Output is correct
6 Correct 801 ms 9816 KB Output is correct
7 Correct 309 ms 9816 KB Output is correct
8 Correct 779 ms 9820 KB Output is correct
9 Correct 1016 ms 9816 KB Output is correct
10 Correct 29 ms 9816 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 10 ms 9816 KB Output is correct
13 Correct 9 ms 9816 KB Output is correct
14 Correct 5 ms 9816 KB Output is correct
15 Correct 33 ms 9832 KB Output is correct
16 Correct 760 ms 9824 KB Output is correct
17 Correct 768 ms 9816 KB Output is correct
18 Correct 309 ms 9820 KB Output is correct
19 Correct 819 ms 9816 KB Output is correct
20 Correct 1018 ms 9820 KB Output is correct
21 Correct 36 ms 9816 KB Output is correct
22 Correct 33 ms 9816 KB Output is correct
23 Correct 2298 ms 9820 KB Output is correct
24 Runtime error 21 ms 19556 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -