oj.uz

Submission #596304

# Submission time Handle Problem Language Result Execution time Memory
596304 2022-07-14T14:57:33 Z kshitij_sodani Uplifting Excursion (BOI22_vault) C++14
10 / 100
 5000 ms 1656 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];
deque<pair<llo,llo>> zz[301];
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(n,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(int jj=0;jj<j;jj++){
				zz[jj].clear();
			}
			for(int ii=0;ii<=su3;ii++){
				int y=ii%j;
				if(dp[ii]>=0){
					pair<int,int> cur={dp[ii]-(ii/j),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-j*min(it[j],n)){
						zz[y].pop_front();
					}
					else{
						break;
					}
				}
				if(zz[y].size()){
					llo xx=zz[y].front().a+(ii/j) ;
					if(dp[ii]==-1){
						dp[ii]=xx;
					}
					dp[ii]=min(dp[ii],xx);
				}
			}
		/*	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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Execution timed out 5031 ms 1632 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Execution timed out 5031 ms 1632 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 468 KB Output is correct
2 Correct 37 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 189 ms 744 KB Output is correct
5 Correct 37 ms 724 KB Output is correct
6 Correct 316 ms 744 KB Output is correct
7 Correct 138 ms 724 KB Output is correct
8 Correct 126 ms 724 KB Output is correct
9 Correct 118 ms 732 KB Output is correct
10 Correct 82 ms 816 KB Output is correct

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 37 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 189 ms 744 KB Output is correct
5 Correct 37 ms 724 KB Output is correct
6 Correct 316 ms 744 KB Output is correct
7 Correct 138 ms 724 KB Output is correct
8 Correct 126 ms 724 KB Output is correct
9 Correct 118 ms 732 KB Output is correct
10 Correct 82 ms 816 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 38 ms 852 KB Output is correct
16 Correct 6 ms 724 KB Output is correct
17 Correct 196 ms 744 KB Output is correct
18 Correct 35 ms 724 KB Output is correct
19 Correct 306 ms 856 KB Output is correct
20 Correct 137 ms 724 KB Output is correct
21 Correct 126 ms 724 KB Output is correct
22 Correct 114 ms 736 KB Output is correct
23 Correct 82 ms 744 KB Output is correct
24 Incorrect 200 ms 736 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 468 KB Output is correct
2 Correct 37 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 189 ms 744 KB Output is correct
5 Correct 37 ms 724 KB Output is correct
6 Correct 316 ms 744 KB Output is correct
7 Correct 138 ms 724 KB Output is correct
8 Correct 126 ms 724 KB Output is correct
9 Correct 118 ms 732 KB Output is correct
10 Correct 82 ms 816 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 36 ms 724 KB Output is correct
13 Correct 7 ms 736 KB Output is correct
14 Correct 184 ms 732 KB Output is correct
15 Correct 35 ms 736 KB Output is correct
16 Correct 324 ms 736 KB Output is correct
17 Correct 136 ms 728 KB Output is correct
18 Correct 129 ms 724 KB Output is correct
19 Correct 113 ms 748 KB Output is correct
20 Correct 83 ms 744 KB Output is correct
21 Correct 1707 ms 1492 KB Output is correct
22 Correct 1664 ms 1496 KB Output is correct
23 Correct 107 ms 1492 KB Output is correct
24 Correct 46 ms 1512 KB Output is correct
25 Correct 213 ms 1540 KB Output is correct
26 Correct 3813 ms 1656 KB Output is correct
27 Execution timed out 5019 ms 1640 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Execution timed out 5031 ms 1632 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 468 KB Output is correct
2 Correct 37 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 189 ms 744 KB Output is correct
5 Correct 37 ms 724 KB Output is correct
6 Correct 316 ms 744 KB Output is correct
7 Correct 138 ms 724 KB Output is correct
8 Correct 126 ms 724 KB Output is correct
9 Correct 118 ms 732 KB Output is correct
10 Correct 82 ms 816 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 36 ms 724 KB Output is correct
13 Correct 7 ms 736 KB Output is correct
14 Correct 184 ms 732 KB Output is correct
15 Correct 35 ms 736 KB Output is correct
16 Correct 324 ms 736 KB Output is correct
17 Correct 136 ms 728 KB Output is correct
18 Correct 129 ms 724 KB Output is correct
19 Correct 113 ms 748 KB Output is correct
20 Correct 83 ms 744 KB Output is correct
21 Correct 1707 ms 1492 KB Output is correct
22 Correct 1664 ms 1496 KB Output is correct
23 Correct 107 ms 1492 KB Output is correct
24 Correct 46 ms 1512 KB Output is correct
25 Correct 213 ms 1540 KB Output is correct
26 Correct 3813 ms 1656 KB Output is correct
27 Execution timed out 5019 ms 1640 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Execution timed out 5031 ms 1632 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 468 KB Output is correct
2 Correct 37 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 189 ms 744 KB Output is correct
5 Correct 37 ms 724 KB Output is correct
6 Correct 316 ms 744 KB Output is correct
7 Correct 138 ms 724 KB Output is correct
8 Correct 126 ms 724 KB Output is correct
9 Correct 118 ms 732 KB Output is correct
10 Correct 82 ms 816 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 36 ms 724 KB Output is correct
13 Correct 7 ms 736 KB Output is correct
14 Correct 184 ms 732 KB Output is correct
15 Correct 35 ms 736 KB Output is correct
16 Correct 324 ms 736 KB Output is correct
17 Correct 136 ms 728 KB Output is correct
18 Correct 129 ms 724 KB Output is correct
19 Correct 113 ms 748 KB Output is correct
20 Correct 83 ms 744 KB Output is correct
21 Correct 1707 ms 1492 KB Output is correct
22 Correct 1664 ms 1496 KB Output is correct
23 Correct 107 ms 1492 KB Output is correct
24 Correct 46 ms 1512 KB Output is correct
25 Correct 213 ms 1540 KB Output is correct
26 Correct 3813 ms 1656 KB Output is correct
27 Execution timed out 5019 ms 1640 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

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