Submission #937109

#	Time	Username	Problem	Language	Result	Execution time	Memory
937109		berr	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	420 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(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]-=n;
            }
        }
 
        if(sum>m){
            cout<<"impossible";
            return 0;
        }
        else hedef = m-sum;
    }
    else{
        int sum=0;
        for(int i=n; i>0; i--){
            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> vis1(n*2+1), val(n*2+1, 1e18);
 
 
    val[n]=0;
 
    int mi=0;
    int pf=1;
    int h=5000;
    while(pf){
        int flag = 0;
        vector<int> pre;
        pre = val;
 
        for(int i=-n; i<=n&&!flag; i++){
            if(used[i+n]>0){
                for(int l=-n; l<=n; l++){
                    if(l-i>=-n&&l-i<=n)
                    if(pre[l+n]==mi && val[(l-i)+n] >=mi){
                        flag = 1;
                        val[(l-i+n)]=mi-1;
                    }
                }
 
                if(flag){
                    used[i+n]--; mi--;
                }
            }
        }
        if(!flag){
            int check = 0;
            for(int i=-n; i<=n; i++){
                int check2=0;
                if(a[i+n]>0){
                    for(int l=-n; l<=n; l++){
                        if(l+i>=-n && l+i<=n){
                            if(val[l+n]==mi && val[(l+i)+n]>mi+1){
                                check2 = 1;
                                val[(l+i)+n] = mi+1;
                            }
                        }
                    }
 
                    if(check2) a[i+n]--;
                }
            }

            for(int l=-n; l<=n; l++){
                if(val[l+n]==mi) check=1;
            }
            if(check) mi++;
            else pf=0;
        }
        
    }
 
    if(val[hedef+n]!=1e18){
        cout<<el-(top+val[hedef+n]);
    }   
    else cout<<"impossible";
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:95:9: warning: unused variable 'h' [-Wunused-variable]
   95 |     int h=5000;
      |         ^

• 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