Submission #653526

#	Time	Username	Problem	Language	Result	Execution time	Memory
653526		erto	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	340 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){
            cout << "impossible";
            return;
        }
        bool bb = 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)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<=99000; j++){
                if(dp2[j] > 0 && dp1[j - dif] > 0){
                    bb = 1;
                    ans -= f1(j - dif);
                    ans += f2(j);
                }
            }
            if(bb)break;
        }

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

        cout << ans;
    }


    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