Submission #653552

#	Time	Username	Problem	Language	Result	Execution time	Memory
653552		AlperenT	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	301 ms	12180 KiB

vault

#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]){
                memset(old, 0, sizeof(old));

                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(!dq.empty() && 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]){
                memset(old, 0, sizeof(old));

                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(!dq.empty() && 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 && i - l < N && 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
• 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