Submission #778859

#	Time	Username	Problem	Language	Result	Execution time	Memory
778859		new_acc	Uplifting Excursion (BOI22_vault)	C++14	100 / 100	877 ms	2132 KiB

vault

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=300+10;
const int M=302*300;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const int L=20;
int n;
ll t[N*2],l,doz[N*2][2];
int p1[M*2+10],p2[M*2+10];
void add(int val,ll il,bool xd){
    if(!il) return;
    bool rev=0;
    for(int i=0;i<=M*2;i++){
        p2[i]=-INFi;
    }
    if(val<0){
        for(int i=0;i<M;i++){
            swap(p1[i],p1[M*2-i]);
        }
        rev=1;
        val*=(-1);
    }
    for(int i=0;i<val;i++){
        deque<pair<int,int> >kol;
        for(int i2=0;i2*val+i<=M*2;i2++){
            int id=i2*val+i;
            int cval=p1[id];
            if(xd) cval-=i2;
            else cval+=i2;
            if(p1[id]!=-INFi){
                while(kol.size() and kol.back().fi<=cval){
                    kol.pop_back();
                }
                kol.push_back({cval,i2});
            }
            if(kol.size() and i2-kol.front().se==il+1){
                kol.pop_front();
            }
            if(kol.size()){
                p2[id]=max(p2[id],(xd?i2:-i2)+kol.front().fi);
            }
        }
    }
    if(rev){
        for(int i=0;i<M;i++){
            swap(p1[i],p1[M*2-i]);
            swap(p2[i],p2[M*2-i]);
        }
    }
    for(int i=0;i<=M*2;i++){
        p1[i]=max(p1[i],p2[i]);
    }
}
ll pl(int val){
    for(int i=0;i<=M*2;i++) p1[i]=-INFi;
    p1[M]=0;
    for(int i=0;i<=n*2;i++){
        add(i-n,doz[i][0],0);
        add(i-n,doz[i][1],1);
    }
    return p1[val+M];
}
void solve(){
    cin>>n>>l;
    ll sum=0;
    for(int i=-n;i<=n;i++){
        cin>>t[i+n];
        sum+=t[i+n]*(ll)i;
    }
    if(sum<=l){
        l*=(ll)(-1); 
        for(int i=0;i<n;i++){
            swap(t[i],t[n*2-i]);
        }
    }
    ll curr=0,res=0;
    for(int i=-n;i<=n;i++){
        if(i<=0){
            curr+=t[i+n]*(ll)i;
            doz[-i+n][0]+=t[i+n];
            res+=t[i+n];
            continue;
        }
        int id=i+n;
        ll r=l-curr;
        ll il=(r+i-1)/(ll)i;
        il=min(il,t[i+n]);
        if(r<0) il=0;
        curr+=il*(ll)i;
        res+=il;
        if(il==0){
            doz[i+n][1]+=t[i+n]; 
            continue;
        }
        if(il==t[i+n]){
            doz[-i+n][0]+=t[i+n];
        }else{
            doz[-i+n][0]+=il;
            doz[i+n][1]+=(t[i+n]-il);
        }
    }
    if(abs(l-curr)>(ll)300){
        cout<<"impossible\n";
        return;
    }
    ll ans=pl(l-curr);
    if(ans==-INFi) cout<<"impossible\n";
    else cout<<res+ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message (stderr)

vault.cpp: In function 'void solve()':
vault.cpp:96:13: warning: unused variable 'id' [-Wunused-variable]
   96 |         int id=i+n;
      |             ^~

• 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