oj.uz

Submission #653534

# Submission time Handle Problem Language Result Execution time Memory
653534 2022-10-27T08:34:39 Z AlperenT Uplifting Excursion (BOI22_vault) C++17
0 / 100
 28 ms 16468 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 505000 + 5;

long long m, l, pos[N], old[N], neg[N], ans = -1;

vector<int> negw, posw;

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

    cin >> m >> l;

    negw = posw = vector(m + 1, 0);

    for(int i = m; i >= 1; i--) cin >> negw[i];

    for(int i = 0; i <= m; i++) cin >> posw[i];

    if(abs(l) >= N) cout << "impossible";
    else{
        pos[0] = 1;

        for(int x = 1; x <= m; x++){
            if(posw[x]){
                for(int md = 0; md < x; md++){
                    deque<int> dq;

                    for(int i = md; i < N; i += x){
                        old[i] = pos[i];

                        pos[i] = max(pos[i], dq.empty() ? 0ll : dq.front() + i / x);

                        if(i - x * posw[x] >= 0 && old[i - x * posw[x]] != 0 && dq.back() == old[i - x * posw[x]] - (i - x * posw[x]) / x){
                            dq.pop_back();
                        }

                        if(old[i] != 0){
                            while(!dq.empty() && dq.back() < old[i] - i / x) dq.pop_back();
                            dq.push_back(old[i] - i / x);
                        }
                    }
                }
            }
        }

        for(int i = 0; i < N; i++) pos[i] -= 1;

        neg[0] = 1;

        for(int x = 1; x <= m; x++){
            if(negw[x]){
                for(int md = 0; md < x; md++){
                    deque<int> dq;

                    for(int i = md; i < N; i += x){
                        old[i] = neg[i];

                        neg[i] = max(neg[i], dq.empty() ? 0ll : dq.front() + i / x);

                        if(i - x * negw[x] >= 0 && old[i - x * negw[x]] != 0 && dq.back() == old[i - x * negw[x]] - (i - x * negw[x]) / x){
                            dq.pop_back();
                        }

                        if(old[i] != 0){
                            while(!dq.empty() && dq.back() < old[i] - i / x) dq.pop_back();
                            dq.push_back(old[i] - i / x);
                        }
                    }
                }
            }
        }

        for(int i = 0; i < N; i++) neg[i] -= 1;

        if(l < 0 && neg[-l] > 0) ans = neg[-l];
        else if(l == 0) ans = 0;
        else if(l > 0 && pos[l] > 0) ans = pos[l];

        for(int i = 1; i < N; i++){
            if(pos[i] > 0 && i - l >= 1 && neg[i - l] > 0){
                ans = max(ans, pos[i] + neg[i - l]);
            }
        } 

        if(ans == -1) cout << "impossible";
        else cout << ans + posw[0];
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Runtime error 28 ms 16448 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Runtime error 28 ms 16448 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Runtime error 28 ms 16448 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Runtime error 28 ms 16448 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 16468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Runtime error 28 ms 16448 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -