oj.uz

Submission #596298

# Submission time Handle Problem Language Result Execution time Memory
596298 2022-07-14T14:47:40 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
10 / 100
 5000 ms 1236 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;
		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=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++;
				}
			}
		}
		llo cur2=cur-su2;

		for(llo j=0;j<=su3;j++){
			if(cur2>=j and 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;
						}
					/*	
						if(y==11){
							cout<<dp[j]<<endl;
							cout<<cur2<<",,,,"<<su2<<endl;
							cout<<i<<"::"<<j<<endl;
						}*/
						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 212 KB Output is correct
2 Correct 0 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 5051 ms 1236 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 5051 ms 1236 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 202 ms 540 KB Output is correct
3 Correct 42 ms 468 KB Output is correct
4 Correct 552 ms 528 KB Output is correct
5 Correct 150 ms 468 KB Output is correct
6 Correct 727 ms 528 KB Output is correct
7 Correct 631 ms 524 KB Output is correct
8 Correct 550 ms 524 KB Output is correct
9 Correct 516 ms 528 KB Output is correct
10 Correct 373 ms 588 KB Output is correct

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 202 ms 540 KB Output is correct
3 Correct 42 ms 468 KB Output is correct
4 Correct 552 ms 528 KB Output is correct
5 Correct 150 ms 468 KB Output is correct
6 Correct 727 ms 528 KB Output is correct
7 Correct 631 ms 524 KB Output is correct
8 Correct 550 ms 524 KB Output is correct
9 Correct 516 ms 528 KB Output is correct
10 Correct 373 ms 588 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 173 ms 524 KB Output is correct
16 Correct 34 ms 468 KB Output is correct
17 Correct 550 ms 532 KB Output is correct
18 Correct 157 ms 528 KB Output is correct
19 Correct 738 ms 524 KB Output is correct
20 Correct 559 ms 524 KB Output is correct
21 Correct 583 ms 532 KB Output is correct
22 Correct 520 ms 524 KB Output is correct
23 Correct 378 ms 536 KB Output is correct
24 Incorrect 552 ms 528 KB Output isn't correct
25 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 202 ms 540 KB Output is correct
3 Correct 42 ms 468 KB Output is correct
4 Correct 552 ms 528 KB Output is correct
5 Correct 150 ms 468 KB Output is correct
6 Correct 727 ms 528 KB Output is correct
7 Correct 631 ms 524 KB Output is correct
8 Correct 550 ms 524 KB Output is correct
9 Correct 516 ms 528 KB Output is correct
10 Correct 373 ms 588 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 172 ms 588 KB Output is correct
13 Correct 34 ms 524 KB Output is correct
14 Correct 539 ms 524 KB Output is correct
15 Correct 149 ms 524 KB Output is correct
16 Correct 740 ms 520 KB Output is correct
17 Correct 561 ms 536 KB Output is correct
18 Correct 540 ms 528 KB Output is correct
19 Correct 512 ms 536 KB Output is correct
20 Correct 366 ms 524 KB Output is correct
21 Execution timed out 5086 ms 1236 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 5051 ms 1236 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 202 ms 540 KB Output is correct
3 Correct 42 ms 468 KB Output is correct
4 Correct 552 ms 528 KB Output is correct
5 Correct 150 ms 468 KB Output is correct
6 Correct 727 ms 528 KB Output is correct
7 Correct 631 ms 524 KB Output is correct
8 Correct 550 ms 524 KB Output is correct
9 Correct 516 ms 528 KB Output is correct
10 Correct 373 ms 588 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 172 ms 588 KB Output is correct
13 Correct 34 ms 524 KB Output is correct
14 Correct 539 ms 524 KB Output is correct
15 Correct 149 ms 524 KB Output is correct
16 Correct 740 ms 520 KB Output is correct
17 Correct 561 ms 536 KB Output is correct
18 Correct 540 ms 528 KB Output is correct
19 Correct 512 ms 536 KB Output is correct
20 Correct 366 ms 524 KB Output is correct
21 Execution timed out 5086 ms 1236 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 5051 ms 1236 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 202 ms 540 KB Output is correct
3 Correct 42 ms 468 KB Output is correct
4 Correct 552 ms 528 KB Output is correct
5 Correct 150 ms 468 KB Output is correct
6 Correct 727 ms 528 KB Output is correct
7 Correct 631 ms 524 KB Output is correct
8 Correct 550 ms 524 KB Output is correct
9 Correct 516 ms 528 KB Output is correct
10 Correct 373 ms 588 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 172 ms 588 KB Output is correct
13 Correct 34 ms 524 KB Output is correct
14 Correct 539 ms 524 KB Output is correct
15 Correct 149 ms 524 KB Output is correct
16 Correct 740 ms 520 KB Output is correct
17 Correct 561 ms 536 KB Output is correct
18 Correct 540 ms 528 KB Output is correct
19 Correct 512 ms 536 KB Output is correct
20 Correct 366 ms 524 KB Output is correct
21 Execution timed out 5086 ms 1236 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 5051 ms 1236 KB Time limit exceeded
6 Halted 0 ms 0 KB -