oj.uz

Submission #596277

# Submission time Handle Problem Language Result Execution time Memory
596277 2022-07-14T14:33:19 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
0 / 100
 5000 ms 1296 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 dp[1000001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>dd;
	llo cot=0;
	for(llo i=0;i<n;i++){
		llo aa;
		cin>>aa;
		cot+=aa;
	}
	llo su=0;
	for(llo i=0;i<=n;i++){
		cin>>it[i];
		su+=it[i]*i;
		cot+=it[i];
	}
	if(su<dd){
		cout<<"impossible"<<endl;
		return 0;
	}
	llo cur=su-dd;
	it[0]=0;
	llo ans=-1;
	for(llo i=1;i<=n;i++){
		llo su2=0;
		for(llo j=i+1;j<=n;j++){
			llo xx=it[j]-n;
			if(xx<0){
				xx=0;
			}
			su2+=xx*j;
		}
		if(su2>cur){
			continue;
		}
		llo su3=n*n*n;
		/*for(llo j=1;j<i;j++){
			su3+=j*min(i,it[j]);
		}
		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;
		for(llo j=1;j<i;j++){
			for(llo ii=su3;ii>=0;ii--){
				llo co=0;
				for(llo jj=ii;jj>=0 and jj>=ii-j*n;jj-=j){
					if(dp[jj]>=0){
						llo xx=dp[jj]+co;
						if(co>it[j]){
							continue;
						}
						if(dp[ii]==-1){
							dp[ii]=xx;
						}
						dp[ii]=min(dp[ii],xx);
					}
					co++;
				}
			}
		}
		for(llo j=i+1;j<=n;j++){
			for(llo ii=su3;ii>=0;ii--){
				llo co=0;
				for(llo jj=ii;jj>=0 and jj>=ii-j*min(it[j],n);jj-=j){
					if(dp[jj]>=0){
						llo xx=dp[jj]+co;
/*						if(co>min(it[j],n)){
							continue;
						}*/
						if(dp[ii]==-1){
							dp[ii]=xx;
						}
						dp[ii]=min(dp[ii],xx);
					}
					co++;
				}
			}
		}
		for(llo j=0;j<=su3;j++){
			if(cur>=j and dp[j]>=0){
				if((cur-j)%i==0){
					llo x=(cur-j)/i;
					if(x<=it[i]){
						llo y=dp[j]+x;
						if(ans==-1){
							ans=y;
						}
						ans=min(ans,y);
					}
				}
			}
		}

	}
	if(ans==-1){
		cout<<"impossible"<<endl;
	}
	else{
		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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5056 ms 1296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5056 ms 1296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 524 KB Output is correct
3 Correct 30 ms 468 KB Output is correct
4 Incorrect 468 ms 528 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 212 KB Output is correct
2 Correct 147 ms 524 KB Output is correct
3 Correct 30 ms 468 KB Output is correct
4 Incorrect 468 ms 528 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 212 KB Output is correct
2 Correct 147 ms 524 KB Output is correct
3 Correct 30 ms 468 KB Output is correct
4 Incorrect 468 ms 528 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5056 ms 1296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 524 KB Output is correct
3 Correct 30 ms 468 KB Output is correct
4 Incorrect 468 ms 528 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5056 ms 1296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 524 KB Output is correct
3 Correct 30 ms 468 KB Output is correct
4 Incorrect 468 ms 528 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5056 ms 1296 KB Time limit exceeded
6 Halted 0 ms 0 KB -