Submission #653550

#	Time	Username	Problem	Language	Result	Execution time	Memory
653550		erto	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1229 ms	1888 KiB

vault

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF (int)(1e9 + 7)
#define INF2 998244353
#define N (ll)(3e2 + 5)
//#define f first
//#define s second
#define int ll
#define lsb(x) (x & (-x))
using namespace std;

int n, m, g, h, l;

int a[1000];
int dp1[100000], dp2[100000];
int cnt1[100000], cnt2[100000];
int sum = 0;

int f1(int x){
    int sum = 0;
    while(x){
        sum += cnt1[x];
        x -= cnt1[x] * dp1[x];
    }
    return sum;
}

int f2(int x){
    int sum = 0;
    while(x){
        sum += cnt2[x];
        x -= cnt2[x] * dp2[x];
    }
    return sum;
}

void solve(){
    cin >> m >> l;
    for(int i=0; i<2*m+1; i++){
        cin >> a[i];
        if(i > m){
            sum += (i - m) * a[i];
        }
    }

    int ans = a[m];
    int cur = 0;
    int t1, t2;

    dp1[0] = dp2[0] = 1;

    if(sum < l || l < 0){
        cout << "impossible";
        return;
    }
    bool bb = 0;

    int maxx = 0;

    for(int i=m+1; i<=2*m; i++){
        g = (l - cur) / (i - m);
        h = min(g, a[i]);
        ans += h;
        cur += h * (i - m);
        t1 = h;
        t2 = a[i] - h;

        if(cur == l){
            maxx = ans;
            bb=1;
            break;
        }

        for(int k=99000; k; k--){
            if(dp1[k])continue;
            for(int j=1; j<=t1 && j * (i - m) <= k; j++){
                if(dp1[k - j * (i - m)]){
                    dp1[k] = (i - m);
                    cnt1[k] = j;
                }
            }
        }

        for(int k=99000; k; k--){
            if(dp2[k])continue;
            for(int j=1; j<=t2 && j * (i - m) <= k; j++){
                if(dp2[k - j * (i - m)]){
                    dp2[k] = (i - m);
                    cnt2[k] = j;
                }
            }
        }

        int dif = l - cur;
        for(int j=dif; j<=min(l, 99000ll); j++){
            if(dp2[j] > 0 && dp1[j - dif] > 0){
                bb = 1;
                maxx = max(maxx, ans + f2(j) - f1(j - dif));
            }
        }
    }

    if(!bb){
        cout << "impossible";
        return;
    }

    cout <<maxx;
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin>>T;
    for(int i=1; i<=T; i++){
        solve();
    }
}

• 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