oj.uz

답안 #596387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596387 2022-07-14T16:34:31 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
0 / 100
 1 ms 852 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=0;

void apply(int l,int r){
	for(int j=l;j<=r;j++){

		llo ax=j*min(it[j],n);
		su3+=ax;
		llo y=0;
		llo z=0;
		//llo su3=n*n*n;
		for(int i=0;i<j;i++){
			zz[i].clear();
		}
		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++;
			}
		}
	}
}
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){
	if(l==r){
		llo ac=0;
		llo ac2=0;
		for(int j=r+1;j<=n;j++){
			ac+=((it[j]-min(it[j],n)))*j;
			ac2+=(it[j]-min(it[j],n));
		}

		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+=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);
		llo su4=su3;
		solve(mid+1,r);

		remove(l,mid);
		for(int ii=0;ii<dp2.size();ii++){
			dp[ii]=dp2[ii];
		}
		for(int ii=su3+1;ii<=su4;ii++){
			dp[ii]=-1;
		}
		apply(mid+1,r);
		su4=su3;
		solve(l,mid);
		remove(l,mid);
		for(int ii=0;ii<dp2.size();ii++){
			dp[ii]=dp2[ii];
		}
		for(int ii=su3+1;ii<=su4;ii++){
			dp[ii]=-1;
		}
		

	}



}
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=0;
	if(su<dd){
		cout<<"impossible"<<endl;
		return 0;
	}
	llo cur=su-dd;
	pp=cur;
	it[0]=0;
		for(int i=0;i<=n*n*n;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;
}

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 1 ms 852 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 1 ms 852 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 1 ms 852 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 1 ms 852 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Runtime error 1 ms 852 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -