제출 #721638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721638		The_Samurai	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	4 ms	724 KiB

vault

#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, -INF), dp_minus(N, -INF);
        dp_plus[0] = dp_minus[0] = 0;
        if (l > N) {
            cout << "impossible";
            return;
        }
        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
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10