oj.uz

Submission #788222

# Submission time Handle Problem Language Result Execution time Memory
788222 2023-07-20T02:44:30 Z Ozy Uplifting Excursion (BOI22_vault) C++17
0 / 100
 91 ms 23812 KB 
#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;
    cout << res;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8208 KB Output is correct
2 Correct 10 ms 8132 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 21 ms 8184 KB Output is correct
5 Runtime error 91 ms 18388 KB Execution killed with signal 7
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8208 KB Output is correct
2 Correct 10 ms 8132 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 21 ms 8184 KB Output is correct
5 Runtime error 91 ms 18388 KB Execution killed with signal 7
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8260 KB Output is correct
2 Incorrect 84 ms 23812 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 22 ms 8260 KB Output is correct
2 Incorrect 84 ms 23812 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 22 ms 8260 KB Output is correct
2 Incorrect 84 ms 23812 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 10 ms 8208 KB Output is correct
2 Correct 10 ms 8132 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 21 ms 8184 KB Output is correct
5 Runtime error 91 ms 18388 KB Execution killed with signal 7
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8260 KB Output is correct
2 Incorrect 84 ms 23812 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 10 ms 8208 KB Output is correct
2 Correct 10 ms 8132 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 21 ms 8184 KB Output is correct
5 Runtime error 91 ms 18388 KB Execution killed with signal 7
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8260 KB Output is correct
2 Incorrect 84 ms 23812 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 10 ms 8208 KB Output is correct
2 Correct 10 ms 8132 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 21 ms 8184 KB Output is correct
5 Runtime error 91 ms 18388 KB Execution killed with signal 7
6 Halted 0 ms 0 KB -