oj.uz

Submission #599206

# Submission time Handle Problem Language Result Execution time Memory
599206 2022-07-19T11:40:05 Z SlavicG Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

vector<int> calc(vector<int> x) {
    int S = (int)x.size() * 100;
    vector<int> dp(S + 1, INT_MIN);
    dp[0] = 0;
    for(int i = 0; i < (int)x.size(); ++i) {
        for(int j = S; j >= 0; --j) {
            if(j - x[i] >= 0) if(dp[j - x[i]] != INT_MIN) dp[j] = max(dp[j], dp[j - x[i]] + 1);
        }
    }
    return dp;
}
int main() {
    ll l, m; cin >> m >> l;
    vector<int> a(2 * m + 1);
    for(int i = 0; i < 2 * m + 1; ++i) cin >> a[i];

    int ans = INT_MIN;
    vector<int> neg;
    int val = m;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < a[i]; ++j) neg.push_back(val);
        --val;
    }
    vector<int> pos;
    val = 1;
    for(int i = m + 1; i < 2 * m + 1; ++i) {
        for(int j = 0; j < a[i]; ++j) pos.push_back(val);
        ++val;
    }
    vector<int> pp = calc(pos);
    vector<int> ng = calc(neg);

    if(l < 0) {
        swap(pp, ng);
        l = -l;
    }
    for(ll sum = l; sum < (int)pp.size(); ++sum) {
        if(sum - l >= (int)ng.size() || pp[sum] == INT_MIN || ng[sum - l] == INT_MIN) continue;
        ans = max(ans, pp[sum] + ng[sum - l] + a[m]);
    }
    if(ans == INT_MIN) cout << "impossible\n";
    else cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 236 ms 1292 KB Output is correct
6 Correct 250 ms 1352 KB Output is correct
7 Correct 70 ms 716 KB Output is correct
8 Correct 267 ms 1192 KB Output is correct
9 Correct 908 ms 2152 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 236 ms 1292 KB Output is correct
6 Correct 250 ms 1352 KB Output is correct
7 Correct 70 ms 716 KB Output is correct
8 Correct 267 ms 1192 KB Output is correct
9 Correct 908 ms 2152 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 301 ms 1292 KB Output is correct
17 Correct 297 ms 1360 KB Output is correct
18 Correct 65 ms 720 KB Output is correct
19 Correct 249 ms 1308 KB Output is correct
20 Correct 952 ms 2188 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 4069 ms 4336 KB Output is correct
24 Correct 3940 ms 4300 KB Output is correct
25 Correct 538 ms 1832 KB Output is correct
26 Execution timed out 5050 ms 4180 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 212 KB Output is correct
2 Runtime error 554 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 1 ms 212 KB Output is correct
2 Runtime error 554 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 1 ms 212 KB Output is correct
2 Runtime error 554 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 236 ms 1292 KB Output is correct
6 Correct 250 ms 1352 KB Output is correct
7 Correct 70 ms 716 KB Output is correct
8 Correct 267 ms 1192 KB Output is correct
9 Correct 908 ms 2152 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Runtime error 554 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 1 ms 212 KB Output is correct
2 Runtime error 554 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 236 ms 1292 KB Output is correct
6 Correct 250 ms 1352 KB Output is correct
7 Correct 70 ms 716 KB Output is correct
8 Correct 267 ms 1192 KB Output is correct
9 Correct 908 ms 2152 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 301 ms 1292 KB Output is correct
17 Correct 297 ms 1360 KB Output is correct
18 Correct 65 ms 720 KB Output is correct
19 Correct 249 ms 1308 KB Output is correct
20 Correct 952 ms 2188 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 4069 ms 4336 KB Output is correct
24 Correct 3940 ms 4300 KB Output is correct
25 Correct 538 ms 1832 KB Output is correct
26 Execution timed out 5050 ms 4180 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 212 KB Output is correct
2 Runtime error 554 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 236 ms 1292 KB Output is correct
6 Correct 250 ms 1352 KB Output is correct
7 Correct 70 ms 716 KB Output is correct
8 Correct 267 ms 1192 KB Output is correct
9 Correct 908 ms 2152 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 301 ms 1292 KB Output is correct
17 Correct 297 ms 1360 KB Output is correct
18 Correct 65 ms 720 KB Output is correct
19 Correct 249 ms 1308 KB Output is correct
20 Correct 952 ms 2188 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 4069 ms 4336 KB Output is correct
24 Correct 3940 ms 4300 KB Output is correct
25 Correct 538 ms 1832 KB Output is correct
26 Execution timed out 5050 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -