Submission #596383

#	Time	Username	Problem	Language	Result	Execution time	Memory
596383		kshitij_sodani	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	222 ms	8952 KiB

vault

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'


llo n,dd;
llo it[350];

llo cc[601];
llo dp[2000001];
deque<pair<llo,llo>> zz[301];
llo ans=-1;
void apply(int l,int r){
	for(int j=l;j<=r;j++){
		llo ax=j*min(it[j],n);
		llo y=0;
		llo z=0;
		llo su3=n*n*n;
		for(llo ii=0;ii<=su3;ii++){
		//	llo y=ii%j;
			if(dp[ii]>=0){
				pair<llo,llo> cur={dp[ii]-z,ii};
				while(zz[y].size()){
					if(zz[y].back().a>=cur.a){
						zz[y].pop_back();
					}
					else{
						break;
					}
				}
				zz[y].pb(cur);
			}
			while(zz[y].size()){
				if(zz[y].front().b<ii-ax){
					zz[y].pop_front();
				}
				else{
					break;
				}
			}
			if(zz[y].size()){
				llo xx=zz[y].front().a+z;
				if(dp[ii]==-1){
					dp[ii]=xx;
				}
				dp[ii]=min(dp[ii],xx);
			}
			y++;
			if(y==j){
				y=0;
				z++;
			}
		}
	}
}
llo pp;
llo su3=0;
void solve(int l,int r){
	if(l==r){
		llo ac=0;
		for(int j=r+1;j<=n;j++){
			ac+=((it[j]-min(it[j],n)))*j;
		}

		if(ac>pp){
			return;
		}
		llo cur2=pp-ac;
		int i=l;
		//cout<<cur2<<",,"<<ac<<","<<pp<<endl;
		for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){
			if(dp[j]>=0){
				//if((cur2-j)%i==0){
					llo x=(cur2-j)/i;
					if(x<=it[i]){
						llo y=dp[j]+x;
						y+=ac;
						if(ans==-1){
							ans=y;
						}
						ans=min(ans,y);
					}
				//}
			}
		}


	}
	else{
		int mid=(l+r)/2;
		vector<llo> dp2;
		for(int ii=0;ii<=su3;ii++){
			dp2.pb(dp[ii]);
		}
		apply(l,mid);
		solve(mid+1,r);
		for(int ii=0;ii<=su3;ii++){
			dp[ii]=dp2[ii];
		}
		apply(mid+1,r);
		solve(l,mid);
		for(int ii=0;ii<=su3;ii++){
			dp[ii]=dp2[ii];
		}
		

	}



}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>dd;

	llo cot=0;
	llo ma=0;
	llo acc=0;
	for(llo i=0;i<n;i++){
		llo aa;
		cin>>aa;
		cot+=aa;
		cc[i]=aa;
		acc+=aa;
	}
	llo su=0;
	for(llo i=0;i<=n;i++){
		cin>>it[i];
		su+=it[i]*i;
		cot+=it[i];
		cc[n+i]=i;
	}
	for(llo i=0;i<=2*n;i++){
		ma=max(ma,cc[i]);
	}
	su3=n*n*n;
	if(su<dd){
		cout<<"impossible"<<endl;
		return 0;
	}
	llo cur=su-dd;
	pp=cur;
	it[0]=0;
		for(int i=0;i<=su3;i++){
			dp[i]=-1;
		}
		dp[0]=0;
	solve(1,n);
	/*for(llo i=1;i<=n;i++){
		llo su2=0;
		llo ac=0;
		for(llo j=i+1;j<=n;j++){
			llo xx=it[j]-n;
			if(xx<0){
				xx=0;
			}
			ac+=xx;
			su2+=xx*j;
		}
		if(su2>cur){
			continue;
		}
		llo su3=0;//n*n*n;
		for(llo j=1;j<i;j++){
			su3+=j*min(it[j],i);
		}
		for(llo j=i+1;j<=n;j++){
			su3+=j*min(it[j],n);
		}

		for(llo j=0;j<=su3;j++){
			dp[j]=-1;
		}
		dp[0]=0;
		su3=0;
		for(llo j=1;j<=n;j++){
			if(j==i){
				continue;
			}
			if(j<i){
				su3+=j*min(it[j],i);
			}
			else{
				su3+=j*min(it[j],n);
			}
			for(llo jj=0;jj<j;jj++){
				zz[jj].clear();
			}
			llo ax=j*min(it[j],n);
			llo y=0;
			llo z=0;
			for(llo ii=0;ii<=su3;ii++){
			//	llo y=ii%j;
				if(dp[ii]>=0){
					pair<llo,llo> cur={dp[ii]-z,ii};
					while(zz[y].size()){
						if(zz[y].back().a>=cur.a){
							zz[y].pop_back();
						}
						else{
							break;
						}
					}
					zz[y].pb(cur);
				}
				while(zz[y].size()){
					if(zz[y].front().b<ii-ax){
						zz[y].pop_front();
					}
					else{
						break;
					}
				}
				if(zz[y].size()){
					llo xx=zz[y].front().a+z;
					if(dp[ii]==-1){
						dp[ii]=xx;
					}
					dp[ii]=min(dp[ii],xx);
				}
				y++;
				if(y==j){
					y=0;
					z++;
				}
			}

		}

		llo cur2=cur-su2;

		for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){
			if(dp[j]>=0){
				//if((cur2-j)%i==0){
					llo x=(cur2-j)/i;
					if(x<=it[i]){
						llo y=dp[j]+x;
						y+=ac;
						if(ans==-1){
							ans=y;
						}
						ans=min(ans,y);
					}
				//}
			}
		}

	}*/
	if(ans==-1){
		cout<<"impossible"<<endl;
	}
	else{
		//cout<<ans<<endl;
		cout<<cot-ans<<endl;
	}

	//else find minimum number of elements with sum su-dd










	return 0;
}

• 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