Submission #857709

#	Time	Username	Problem	Language	Result	Execution time	Memory
857709		vgtcross	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	3787 ms	9312 KiB

vault

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 1100000;
int dp[N], nx[N];

void solve() {
    int m;
    ll x;
    cin >> m >> x;
    ll mins = 0, maxs = 0;
    vector<pii> v;
    for (int i = -m; i <= m; ++i) {
        int f;
        cin >> f;
        
        if (i < 0) mins += f * i;
        else maxs += f * i;
        
        int z = 1;
        while (f > z) {
            v.push_back({z * i, z});
            f -= z;
            z *= 2;
        }
        if (f > 0) v.push_back({f * i, f});
    }
    
    memset(dp, 0xc0, sizeof dp);
    memset(nx, 0xc0, sizeof nx);
    dp[0] = nx[0] = 0;
    for (pii p : v) {
        for (int i = -550000; i <= 550000; ++i) {
            int j = i + p.first;
            if (-550000 <= j && j <= 550000) nx[(j + N) % N] = max(nx[(j + N) % N], dp[(i + N) % N] + p.second);
        }
        copy(nx, nx+N, dp);
    }
    
    if (x < mins || x > maxs) cout << "impossible\n";
    else cout << (dp[(x + N) % N] < 0 ? "impossible" : to_string(dp[(x + N) % N])) << '\n';
}

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

• 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