oj.uz

Submission #596383

# Submission time Handle Problem Language Result Execution time Memory
596383 2022-07-14T16:26:35 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
0 / 100
 222 ms 8952 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 218 ms 8952 KB Output is correct
6 Incorrect 222 ms 8884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 218 ms 8952 KB Output is correct
6 Incorrect 222 ms 8884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 23 ms 2096 KB Output is correct
4 Incorrect 28 ms 2088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 23 ms 2096 KB Output is correct
4 Incorrect 28 ms 2088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 23 ms 2096 KB Output is correct
4 Incorrect 28 ms 2088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 218 ms 8952 KB Output is correct
6 Incorrect 222 ms 8884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 23 ms 2096 KB Output is correct
4 Incorrect 28 ms 2088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 218 ms 8952 KB Output is correct
6 Incorrect 222 ms 8884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 23 ms 2096 KB Output is correct
4 Incorrect 28 ms 2088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 218 ms 8952 KB Output is correct
6 Incorrect 222 ms 8884 KB Output isn't correct
7 Halted 0 ms 0 KB -