Submission #788243

#	Time	Username	Problem	Language	Result	Execution time	Memory
788243		Ozy	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	213 ms	23756 KiB

vault

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 1000000

lli m,l,res,ceros,a,b,c;
lli arr[2][102];
lli dp[2][MAX+2], usados[MAX+2], existe[2][MAX+2];

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

    cin >> m >> l;
    repa(i,m,1) cin >> arr[0][i];
    cin >> ceros;
    rep(i,1,m) cin >> arr[1][i];

    rep(id,0,1) {
        existe[id][0] = true;

        rep(i,1,m) {
            rep(j,1,MAX) {
                a = j-i;
                usados[j] = 0;

                if(a < 0) continue;
                if (!existe[id][a]) continue;
                if (usados[a] == arr[id][i]) continue; //podrai hacer un berak? segun yo no

                b = dp[id][a]+1;
                if (b > dp[id][j]) {
                    existe[id][j] = 1;
                    usados[j] = usados[a]+1;
                    dp[id][j] = b;
                }
            }
        }

    }

    //rep(id,0,1) {
    //    debug(id);
    //    rep(i,0,15) {
    //        debugsl(i);
    //        debugsl(existe[id][i]);
    //        debug(dp[id][i]);
    //    }
    //}

    res = -1;
    a = 0;
    b = 0;
    if (l < 0) a = -l;
    else b = l;

    rep(i,0,MAX) {
        if( (a+i) > MAX || (b+i) > MAX) break;

        if(!existe[0][i+a] || !existe[1][i+b]) continue;

        c = dp[0][i+a] + dp[1][i+b];
        res = max(res,c);
    }

    if(res == -1) {
        cout << "impossible";
        return 0;
    }

    res += ceros;
    if(res == 0) cout << "impossible";
    else cout << res;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 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