oj.uz

Submission #721635

# Submission time Handle Problem Language Result Execution time Memory
721635 2023-04-11T06:00:01 Z The_Samurai Uplifting Excursion (BOI22_vault) C++17
0 / 100
 92 ms 1460 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

void solve() {
    int n, zero = 0;
    ll l;
    cin >> n >> l;
    vector<ll> a(n), b(n);
    for (ll &x: b) cin >> x;
    cin >> zero;
    for (ll &x: a) cin >> x;
    reverse(b.begin(), b.end());
    if (l < 0) {
        swap(a, b);
        l = -l;
    }
    if (*max_element(a.begin(), a.end()) <= 100) {
        int N = 63751, ans = 0;
        vector<int> dp_plus(N, -1e9), dp_minus(N, -1e9);
        dp_plus[0] = dp_minus[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < a[i]; j++) {
                for (int k = N - 1; k > i; k--) {
                    dp_plus[k] = max(dp_plus[k], dp_plus[k - i - 1] + 1);
                }
            }
            for (int j = 0; j < b[i]; j++) {
                for (int k = N - 1; k > i; k--) {
                    dp_minus[k] = max(dp_minus[k], dp_minus[k - i - 1] + 1);
                }
            }
//            for (int j = 0; j < 100; j++) cout << dp_plus[j] << ' ';
//            cout << '\n';
        }
        for (int i = l; i < N; i++) {
            ans = max(ans, dp_plus[i] + dp_minus[i - l]);
        }
        if (ans == 0) cout << "impossible";
        else cout << ans + zero;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> queries;
#else
//    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 836 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Runtime error 92 ms 1460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 836 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Runtime error 92 ms 1460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 832 KB Output is correct
2 Incorrect 1 ms 212 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 3 ms 832 KB Output is correct
2 Incorrect 1 ms 212 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 3 ms 832 KB Output is correct
2 Incorrect 1 ms 212 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 724 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 836 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Runtime error 92 ms 1460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 832 KB Output is correct
2 Incorrect 1 ms 212 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 724 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 836 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Runtime error 92 ms 1460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 832 KB Output is correct
2 Incorrect 1 ms 212 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 724 KB Output is correct
2 Correct 1 ms 832 KB Output is correct
3 Correct 1 ms 836 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Runtime error 92 ms 1460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -