oj.uz

Submission #728495

# Submission time Handle Problem Language Result Execution time Memory
728495 2023-04-22T14:08:41 Z Charizard2021 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1 ms 300 KB 
#include <bits/stdc++.h>
using namespace std;
void update(int minVal, int S, vector<int> &dp, int l, long long a, int w) {
    if(l > 0){
        for(int i = 0; i < l; i++){
            deque<pair<int, int> > val;
            for(int j = i; j >= 0 && j <= 2 * S; j += l){
                while(!val.empty() && (j - val.front().first)/l > a){
                    val.pop_front();
                }
                while(!val.empty() && dp[j] >= val.back().second + (j - val.back().first)/l * w){
                    val.pop_back();
                }
                if(dp[j] > minVal){
                    val.emplace_back(make_pair(j, dp[j]));
                }
                if(!val.empty()){
                    dp[j] = max(dp[j], val.front().second + (j - val.front().first)/l * w);
                }
            }
        }
    }
    else{
        for(int i = 2 * S; i > 2 * S + l; i--){
            deque<pair<int, int> > val;
            for(int j = i; j >= 0 && j <= 2 * S; j += l){
                while(!val.empty() && (j - val.front().first)/l > a){
                    val.pop_front();
                }
                while(!val.empty() && dp[j] >= val.back().second + (j - val.back().first)/l * w){
                    val.pop_back();
                }
                if(dp[j] > minVal){
                    val.emplace_back(make_pair(j, dp[j]));
                }
                if(!val.empty()){
                    dp[j] = max(dp[j], val.front().second + (j - val.front().first)/l * w);
                }
            }
        }
    }
}

int main() {
    int m;
    cin >> m;
    long long l;
    cin >> l;
    long long x = 0;
    long long sum = 0;
    vector<long long> a(2 * m + 1);
    for(int i = -m; i <= m; i++){
        cin >> a[i + m];
        sum += a[i + m] * i;
    }
    int S = m * m;
    int minVal = -2 * m - 1;
    vector<int> dp(2 * S + 1);
    for(int i = 0; i <= 2 * S; i++){
        dp[i] = minVal;
    }
    dp[S] = 0;
    if(sum < l){
        for (int i = -m; -m <= i && i <= m; i--){
            long long val;
            if(i == 0 || (i > 0) == (-1 < 0)){
                val = a[i + m];
            }
            else{
                val = min(a[i + m], max(0ll, l/i));
            }
            a[i + m] -= val;
            x += val;
            l -= val * i;
            if (i == 0){
                continue;
            }
            update(minVal, S, dp, i, a[i + m], 1);
            update(minVal, S, dp, -i, val, -1);
        }
        if (-S > l || l > S || dp[l + S] == minVal){
            cout << "impossible\n";
        }
        else{
            cout << dp[l + S] + x << "\n";
        }
    }
    else{
        for (int i = -m; -m <= i && i <= m; i--){
            long long val;
            if(i == 0 || (i > 0) == (1 < 0)){
                val = a[i + m];
            }
            else{
                val = min(a[i + m], max(0ll, l/i));
            }
            a[i + m] -= val;
            x += val;
            l -= val * i;
            if (i == 0){
                continue;
            }
            update(minVal, S, dp, i, a[i + m], 1);
            update(minVal, S, dp, -i, val, -1);
        }
        if (-S > l || l > S || dp[l + S] == minVal){
            cout << "impossible\n";
        }
        else{
            cout << dp[l + S] + x << "\n";
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -