oj.uz

Submission #596477

# Submission time Handle Problem Language Result Execution time Memory
596477 2022-07-14T19:11:07 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
10 / 100
 5000 ms 157864 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;
llo su3=2e6;
llo su5=0;
void apply(int l,int r){

	for(int j=l;j<=r;j++){
		if(j==n){
			continue;
		}
		if(j<n){



		}
		llo ax=(j-n)*min(cc[j],n);
		//su3=max(su3,su3+ax);
		//su5=min(su5,su3+ax);
		
		//llo su3=n*n*n;
		for(int i=0;i<abs(j-n);i++){
			zz[i].clear();
		}
		if(j<n){
			continue;
			for(llo ii=su3;ii>=su5;ii--){
				llo y=ii%abs(j-n);
				llo z=ii/abs(j-n);
				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+abs(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++;
				}*/
			}
		}
		else{
			//llo y=0;
			//llo z=0;
			for(llo ii=su5;ii<=su3;ii++){
				llo y=ii%abs(j-n);
				llo z=ii/abs(j-n);
				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);
				}
				
			}
		}
	}
}
void remove(int l,int r){
	/*for(int j=l;j<=r;j++){
		llo ax=j*min(it[j],n);
		su3-=ax;
	}*/
}
llo pp;
void solve(int l,int r){
	//cout<<l<<','<<r<<endl;
	if(l==r){
		if(l==0){
			return;
		}
		llo ac=0;
		llo ac2=0;
		if(l>0){
			for(int j=r+1;j<=2*n;j++){
				ac+=((cc[j]-min(cc[j],n)))*(j-n);
				ac2+=(cc[j]-min(cc[j],n));
			}
			for(int j=0;j<n;j++){
				ac+=((cc[j]-min(cc[j],n)))*(j-n);
				ac2+=(cc[j]-min(cc[j],n));
			}
		}
		else{
			return;
			for(int j=0;j<l;j++){
				ac+=((cc[j]-min(cc[j],n)))*(j-n);
				ac2+=(cc[j]-min(cc[j],n));
			}
			for(int j=n+1;j<=2*n;j++){
				ac+=((cc[j]-min(cc[j],n)))*(j-n);
				ac2+=(cc[j]-min(cc[j],n));
			}
		}

		/*if(ac>pp){
			return;
		}*/
		llo cur2=pp-ac;
		int i=l;
	/*	if(r==4){
			cout<<ac<<":"<<pp<<endl;
		}*/
		//cout<<i<<"::"<<l<<endl;
		//cout<<cur2<<",,"<<ac<<","<<pp<<endl;
		//cout<<dp[n*n*n]<<","<<endl;
		for(llo j=su5;j<=su3;j++){
			if(i==n){
				continue;
			}
	//	for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){
			if(dp[j]>=0){
				/*if(r==4){
					cout<<(j-n*n*n)<<"::"<<endl;
				}*/
				/*if(r==6){
					cout<<(j-n*n*n)<<","<<endl;
				}*/
				//if(l-n==1){
				//cout<<(j-n*n*n)<<":::"<<endl;
				//}
				int ok=1;
				if(i<n){
					ok=-1;
				}
				if(abs(cur2-j)%abs(i-n)==0){
					llo x=abs(cur2-j)/abs(i-n);
					x*=ok;
					if(cur2-j<0){
						x=-x;
					}
					if(x<=cc[i] and x>=0){
						llo y=dp[j]+x;
						y+=ac2;
						if(ans==-1){
							ans=y;
						}
					//	cout<<(j-n*n*n)<<":"<<r<<":"<<pp<<":"<<cur2<<",,"<<x<<endl;
						//cout<<cur2-j<<",,,"<<(i-n)<<",,"<<cc[4]<<endl;
						ans=min(ans,y);
					}
				}
			}
		}
		/*ac=0;
		ac2=0;
		for(int j=0;j<l;j++){
			ac+=((cc[j]-min(cc[j],n)))*(j-n);
			ac2+=(cc[j]-min(cc[j],n));
		}
		cur2=pp-ac;
		for(llo j=su5;j<=su3;j++){
			if(i==n){
				continue;
			}
	//	for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){
			if(dp[j]>=0){
				//if(l-n==1){
				//cout<<(j-n*n*n)<<":::"<<endl;
				//}
				int ok=1;
				if(i<n){
					ok=-1;
				}
				if(abs(cur2-j)%abs(i-n)==0){
					llo x=(cur2-j)/abs(i-n);
					x*=ok;
					if(cur2-j<0){
						x=-x;
					}
					if(x<=cc[i] and x>=0){
						llo y=dp[j]+x;
						y+=ac2;
						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);

		//remove(l,mid);
		for(int ii=0;ii<dp2.size();ii++){
			dp[ii]=dp2[ii];
		}

		apply(mid+1,r);
		solve(l,mid);
		//remove(mid+1,r);
		for(int ii=0;ii<dp2.size();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;
	llo su=0;
	for(llo i=0;i<n;i++){
		llo aa;
		cin>>aa;
		su+=aa*(i-n);
		cot+=aa;
		cc[i]=aa;
		acc+=aa;
	}
	
	for(llo i=0;i<=n;i++){
		cin>>it[i];
		su+=it[i]*i;
		cot+=it[i];
		cc[n+i]=it[i];
	}
	for(llo i=0;i<=2*n;i++){
		ma=max(ma,cc[i]);
	}
	for(int i=1;i<=n;i++){

	}
	//cout<<cc[4]<<":"<<endl;
	//su3=0;
/*	if(su<dd){
		cout<<"impossible"<<endl;
		return 0;
	}*/
	llo cur=su-dd;
	pp=cur;
	pp+=n*n*n;
	it[0]=0;
		for(int i=0;i<=2e6;i++){
			dp[i]=-1;
		}
		dp[(n*n*n)]=0;
	solve(0,2*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;
}

Compilation message

vault.cpp: In function 'void solve(int, int)':
vault.cpp:253:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |   for(int ii=0;ii<dp2.size();ii++){
      |                ~~^~~~~~~~~~~
vault.cpp:260:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |   for(int ii=0;ii<dp2.size();ii++){
      |                ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 79556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 79556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 110972 KB Output is correct
2 Correct 3829 ms 134780 KB Output is correct
3 Correct 3726 ms 126752 KB Output is correct
4 Correct 3654 ms 134920 KB Output is correct
5 Correct 3681 ms 126676 KB Output is correct
6 Correct 3638 ms 126684 KB Output is correct
7 Correct 3632 ms 134784 KB Output is correct
8 Correct 3816 ms 142924 KB Output is correct
9 Correct 4233 ms 126616 KB Output is correct
10 Correct 3874 ms 126728 KB Output is correct

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 110972 KB Output is correct
2 Correct 3829 ms 134780 KB Output is correct
3 Correct 3726 ms 126752 KB Output is correct
4 Correct 3654 ms 134920 KB Output is correct
5 Correct 3681 ms 126676 KB Output is correct
6 Correct 3638 ms 126684 KB Output is correct
7 Correct 3632 ms 134784 KB Output is correct
8 Correct 3816 ms 142924 KB Output is correct
9 Correct 4233 ms 126616 KB Output is correct
10 Correct 3874 ms 126728 KB Output is correct
11 Incorrect 189 ms 79564 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 110972 KB Output is correct
2 Correct 3829 ms 134780 KB Output is correct
3 Correct 3726 ms 126752 KB Output is correct
4 Correct 3654 ms 134920 KB Output is correct
5 Correct 3681 ms 126676 KB Output is correct
6 Correct 3638 ms 126684 KB Output is correct
7 Correct 3632 ms 134784 KB Output is correct
8 Correct 3816 ms 142924 KB Output is correct
9 Correct 4233 ms 126616 KB Output is correct
10 Correct 3874 ms 126728 KB Output is correct
11 Correct 1144 ms 110956 KB Output is correct
12 Correct 4021 ms 134904 KB Output is correct
13 Correct 4006 ms 126700 KB Output is correct
14 Correct 3682 ms 134672 KB Output is correct
15 Correct 3645 ms 126652 KB Output is correct
16 Correct 3618 ms 126648 KB Output is correct
17 Correct 3640 ms 134844 KB Output is correct
18 Correct 3545 ms 143088 KB Output is correct
19 Correct 3654 ms 126864 KB Output is correct
20 Correct 3701 ms 126804 KB Output is correct
21 Execution timed out 5096 ms 157864 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 79556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 110972 KB Output is correct
2 Correct 3829 ms 134780 KB Output is correct
3 Correct 3726 ms 126752 KB Output is correct
4 Correct 3654 ms 134920 KB Output is correct
5 Correct 3681 ms 126676 KB Output is correct
6 Correct 3638 ms 126684 KB Output is correct
7 Correct 3632 ms 134784 KB Output is correct
8 Correct 3816 ms 142924 KB Output is correct
9 Correct 4233 ms 126616 KB Output is correct
10 Correct 3874 ms 126728 KB Output is correct
11 Correct 1144 ms 110956 KB Output is correct
12 Correct 4021 ms 134904 KB Output is correct
13 Correct 4006 ms 126700 KB Output is correct
14 Correct 3682 ms 134672 KB Output is correct
15 Correct 3645 ms 126652 KB Output is correct
16 Correct 3618 ms 126648 KB Output is correct
17 Correct 3640 ms 134844 KB Output is correct
18 Correct 3545 ms 143088 KB Output is correct
19 Correct 3654 ms 126864 KB Output is correct
20 Correct 3701 ms 126804 KB Output is correct
21 Execution timed out 5096 ms 157864 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 79556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 110972 KB Output is correct
2 Correct 3829 ms 134780 KB Output is correct
3 Correct 3726 ms 126752 KB Output is correct
4 Correct 3654 ms 134920 KB Output is correct
5 Correct 3681 ms 126676 KB Output is correct
6 Correct 3638 ms 126684 KB Output is correct
7 Correct 3632 ms 134784 KB Output is correct
8 Correct 3816 ms 142924 KB Output is correct
9 Correct 4233 ms 126616 KB Output is correct
10 Correct 3874 ms 126728 KB Output is correct
11 Correct 1144 ms 110956 KB Output is correct
12 Correct 4021 ms 134904 KB Output is correct
13 Correct 4006 ms 126700 KB Output is correct
14 Correct 3682 ms 134672 KB Output is correct
15 Correct 3645 ms 126652 KB Output is correct
16 Correct 3618 ms 126648 KB Output is correct
17 Correct 3640 ms 134844 KB Output is correct
18 Correct 3545 ms 143088 KB Output is correct
19 Correct 3654 ms 126864 KB Output is correct
20 Correct 3701 ms 126804 KB Output is correct
21 Execution timed out 5096 ms 157864 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 79556 KB Output isn't correct
2 Halted 0 ms 0 KB -