Submission #937171

#	Time	Username	Problem	Language	Result	Execution time	Memory
937171		berr	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	1758 ms	608 KiB

vault

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
       int n, m; cin >> n >> m;
    vector<int> a(n*2+1);
    int sum=0, el = 0, top=0;
 
    for(int i=-1*n; i<=n; i++){
        cin >> a[i+n];
        sum+=i*a[i+n]; el+=a[i+n];
    }
 
    m = sum-m;
    vector<int> used(n*2+1);
    int hedef;
 
    if(m<0){
        int sum=0;
        for(int i=-n; i<0; i++){
            if(a[i+n]==0) continue;
            if(sum+a[i+n]*i > m){
                used[i+n]=a[i+n];
                sum+=a[i+n]*i;
                top+=a[i+n];
                a[i+n]=0;
            }
            else if(sum > m){
                int s=0;
                for(int l=50; l>=0; l--){
                    int tmp = s+(1LL<<l);
                    if(tmp > a[i+n]) continue;
                    if(tmp*i+sum > m){
                        s=tmp;
                    }
                }
                s++;
                sum+=s*i;
                top+=s;
                used[i+n] =s;
                a[i+n]-=s;
            }
        }
 
        if(sum>m){
            cout<<"impossible";
            return 0;
        }
        else hedef = m-sum;
    }
    else{
        int sum=0;
        for(int i=n; i>0; i--){
            if(a[i+n]==0) continue;
            if(sum+a[i+n]*i < m){
                used[i+n]=a[i+n];
                sum+=a[i+n]*i;
                top+=a[i+n];
                a[i+n]=0;
            }
            else if(sum < m){
                int s=0;
                for(int l=50; l>=0; l--){
                    int tmp = s+(1LL<<l);
                    if(tmp > a[i+n]) continue;
                    if(tmp*i+sum < m){
                        s=tmp;
                    }
                }
                s++;
                top+=s;
                sum+=s*i;
                used[i+n] =s;
                a[i+n]-=s;
            }
        }
 
        if(sum<m){
            cout<<"impossible";
            return 0;
        }
        else hedef = m-sum;
    }
 
 
    vector<int>  val(4*n+1, 1e18);
 
    val[2*n]=0;
 
    int mi=0, h=0;
    int pf=1;
 
 
    while(pf){
        h++;
        int flag = 0;
        vector<int> pre;
        pre = val;
 
        for(int i=-n; i<=n; i++){
            if(used[i+n]>0){
                int check =0;
                for(int l=-2*n; l<=2*n; l++){
                    if(l-i>=-2*n&&l-i<=2*n)
                    if(pre[l+2*n]<=mi && val[(l-i)+2*n] > pre[l+2*n]-1){
                        check = 1;
                        val[(l-i+2*n)]=pre[l+2*n]-1;
                    }
                }
 
                if(check){
                    flag = 1;
                    used[i+n]--;
                }
            }
        }
//        if(flag) mi--;
 
        if(!flag){
            int check = 0;
            for(int i=-n; i<=n&&!check; i++){
                int check2=0;
                pre = val;
                if(a[i+n]>0){
                    for(int l=-2*n; l<=2*n; l++){
                        if(l+i>=-2*n && l+i<=2*n){
                            if(val[l+2*n]<=mi && val[(l+i)+2*n]>pre[l+2*n]+1){
                                check2 = 1;
                                val[(l+i)+2*n] = pre[l+2*n]+1;
                            }
                        }
                    }
 
                    if(check2) a[i+n]--, check=1;
                }
            }
 
            for(int l=-2*n; l<=2*n; l++){
                if(val[l+2*n]==mi) check=1;
            }
            if(check) mi++;
            else pf=0;
        }
        
    }
 
 
    if(val[hedef+2*n]!=1e18){
        cout<<el-(top+val[hedef+2*n]);
    }   
    else cout<<"impossible";
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 10 / 10