Submission #595677

#	Time	Username	Problem	Language	Result	Execution time	Memory
595677		definitelynotmee	Uplifting Excursion (BOI22_vault)	C++98	20 / 100	1199 ms	4308 KiB

vault

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1<<30;
const int MAXVAL = 505050;

struct smartvec{
    vector<int> dp;
    smartvec(){
        dp = vector<int>(2*MAXVAL+1,-INF);
    }
    int& operator[](int id){
        return dp[id+MAXVAL];
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll m, l;
    cin >> m >> l;
    if(abs(l) >= MAXVAL){
        cout << "impossible\n";
        return 0;
    }

    vector<pll> v;

    for(int i = -m; i <= m; i++){
        int in;
        cin >> in;
        for(int bit = 0; in; bit++){
            int ct = min(1<<bit,in);
            v.push_back({i*ct,ct});
            in-=ct;
        }
    }
    smartvec dp;
    dp[0] = 0;
    
    for(pii i : v){
        if(i.ff >= 0){
            for(int x = MAXVAL-1; x >= -MAXVAL+i.ff; x--){
                dp[x] = max(dp[x],dp[x-i.ff]+i.ss);
            }
        } else {
            for(int x = -MAXVAL; x < MAXVAL+i.ff; x++){
                dp[x] = max(dp[x],dp[x-i.ff]+i.ss);
            }
        }
        // cout << "iteracao " << i.ff << ' ' << i.ss << "=>" << endl;
        // for(int i = -l; i <= l; i++){
        //     cout << i << ": " << dp[i] << endl;
        // }
    }
    
    if(dp[l] >= 0){
        cout << dp[l] << '\n';
    } else cout << "impossible\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 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