Submission #728485

#	Time	Username	Problem	Language	Result	Execution time	Memory
728485		Charizard2021	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	340 KiB

vault

#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 -= 1){
            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(l == 0){
                val = min(a[i + m], max(0ll, l / i));
            }
            a[i + m] -= val;
            x += val;
            l -= val * i;
            if (l == 0){
                continue;
            }
            update(minVal, S, dp, i, a[l + 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(l == 0 || (l > 0)){
                val = min(a[i + m], max(0ll, l / i));
            }
            a[i + m] -= val;
            x += val;
            l -= val * i;
            if (l == 0){
                continue;
            }
            update(minVal, S, dp, i, a[l + 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";
        }
    }
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:91:22: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |             a[i + m] -= val;
vault.cpp:71:22: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |             l -= val * i;
      |                  ~~~~^~~

• 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