oj.uz

Submission #721803

# Submission time Handle Problem Language Result Execution time Memory
721803 2023-04-11T07:27:44 Z OttincaM Uplifting Excursion (BOI22_vault) C++17
5 / 100
 3955 ms 524288 KB 
#include <iostream>
#include <vector>
#include "stdio.h"
using namespace std;
#define int long long

long long const LLINF = 8e18;
int const N = 400000;
int const ZER = 200000;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    #ifdef WTF
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        freopen("error.txt", "w", stderr);
    #endif


    int m, l; cin >> m >> l;
    vector <int> a(2 * m + 2), x, y, z;
    for(int i = 1; i <= 2 * m + 1; i ++){
         cin >> a[i];
         int K = a[i];
         while(K --){
            if(i - 1 - m > 0){
                x.push_back(i - 1 - m);
            } else if(i - 1 - m < 0){
                y.push_back(i - 1 - m);
            } else {
                z.push_back(i - 1 - m);
            }
         }
    }

    vector <int> dp(N, -LLINF);
    dp[ZER] = (int)z.size();

    for(int t: x){
        for(int i = N - 1; i >= 0; i--){
            if(i - t >= 0 && dp[i - t] != -LLINF){
                dp[i] = max(dp[i], dp[i - t] + 1);
            }
        }

    }

    for(int t: y){
        for(int i = 0; i < N; i ++){
            if(i - t < N && dp[i - t] != -LLINF){
                dp[i] = max(dp[i], dp[i - t] + 1);
            }
        }
    }
        // for(int i = 0; i < N; i ++) cout << dp[i] << " ";

    int ans = -LLINF;
    for(int i = 0; i < N; i ++){
        if(i - ZER == l){
            ans = dp[i]; break;
        }
    }

    if(ans == -LLINF){
        cout << "impossible\n";
    } else {
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Correct 990 ms 3412 KB Output is correct
6 Correct 918 ms 3412 KB Output is correct
7 Correct 344 ms 3412 KB Output is correct
8 Correct 933 ms 3412 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 28 ms 3412 KB Output is correct
11 Correct 26 ms 3412 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Correct 990 ms 3412 KB Output is correct
6 Correct 918 ms 3412 KB Output is correct
7 Correct 344 ms 3412 KB Output is correct
8 Correct 933 ms 3412 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 28 ms 3412 KB Output is correct
11 Correct 26 ms 3412 KB Output is correct
12 Correct 5 ms 3412 KB Output is correct
13 Correct 4 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 17 ms 3412 KB Output is correct
16 Correct 877 ms 3412 KB Output is correct
17 Correct 954 ms 3412 KB Output is correct
18 Correct 354 ms 3412 KB Output is correct
19 Correct 849 ms 3412 KB Output is correct
20 Correct 1685 ms 3540 KB Output is correct
21 Correct 31 ms 3412 KB Output is correct
22 Correct 27 ms 3412 KB Output is correct
23 Correct 3914 ms 3540 KB Output is correct
24 Incorrect 3955 ms 3540 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Output is correct
2 Runtime error 450 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Output is correct
2 Runtime error 450 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Output is correct
2 Runtime error 450 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Correct 990 ms 3412 KB Output is correct
6 Correct 918 ms 3412 KB Output is correct
7 Correct 344 ms 3412 KB Output is correct
8 Correct 933 ms 3412 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 28 ms 3412 KB Output is correct
11 Correct 26 ms 3412 KB Output is correct
12 Correct 25 ms 3412 KB Output is correct
13 Runtime error 450 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Output is correct
2 Runtime error 450 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Correct 990 ms 3412 KB Output is correct
6 Correct 918 ms 3412 KB Output is correct
7 Correct 344 ms 3412 KB Output is correct
8 Correct 933 ms 3412 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 28 ms 3412 KB Output is correct
11 Correct 26 ms 3412 KB Output is correct
12 Correct 5 ms 3412 KB Output is correct
13 Correct 4 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 17 ms 3412 KB Output is correct
16 Correct 877 ms 3412 KB Output is correct
17 Correct 954 ms 3412 KB Output is correct
18 Correct 354 ms 3412 KB Output is correct
19 Correct 849 ms 3412 KB Output is correct
20 Correct 1685 ms 3540 KB Output is correct
21 Correct 31 ms 3412 KB Output is correct
22 Correct 27 ms 3412 KB Output is correct
23 Correct 3914 ms 3540 KB Output is correct
24 Incorrect 3955 ms 3540 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3412 KB Output is correct
2 Runtime error 450 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 17 ms 3412 KB Output is correct
5 Correct 990 ms 3412 KB Output is correct
6 Correct 918 ms 3412 KB Output is correct
7 Correct 344 ms 3412 KB Output is correct
8 Correct 933 ms 3412 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 28 ms 3412 KB Output is correct
11 Correct 26 ms 3412 KB Output is correct
12 Correct 5 ms 3412 KB Output is correct
13 Correct 4 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 17 ms 3412 KB Output is correct
16 Correct 877 ms 3412 KB Output is correct
17 Correct 954 ms 3412 KB Output is correct
18 Correct 354 ms 3412 KB Output is correct
19 Correct 849 ms 3412 KB Output is correct
20 Correct 1685 ms 3540 KB Output is correct
21 Correct 31 ms 3412 KB Output is correct
22 Correct 27 ms 3412 KB Output is correct
23 Correct 3914 ms 3540 KB Output is correct
24 Incorrect 3955 ms 3540 KB Output isn't correct
25 Halted 0 ms 0 KB -