oj.uz

Submission #653552

# Submission time Handle Problem Language Result Execution time Memory
653552 2022-10-27T08:51:01 Z AlperenT Uplifting Excursion (BOI22_vault) C++17
0 / 100
 301 ms 12180 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]){
                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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 27 ms 12072 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 301 ms 12180 KB Output is correct
7 Incorrect 218 ms 12180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 27 ms 12072 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 301 ms 12180 KB Output is correct
7 Incorrect 218 ms 12180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12076 KB Output is correct
2 Incorrect 0 ms 212 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 32 ms 12076 KB Output is correct
2 Incorrect 0 ms 212 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 32 ms 12076 KB Output is correct
2 Incorrect 0 ms 212 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 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 27 ms 12072 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 301 ms 12180 KB Output is correct
7 Incorrect 218 ms 12180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12076 KB Output is correct
2 Incorrect 0 ms 212 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 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 27 ms 12072 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 301 ms 12180 KB Output is correct
7 Incorrect 218 ms 12180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12076 KB Output is correct
2 Incorrect 0 ms 212 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 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 27 ms 12072 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 301 ms 12180 KB Output is correct
7 Incorrect 218 ms 12180 KB Output isn't correct
8 Halted 0 ms 0 KB -