oj.uz

Submission #601194

# Submission time Handle Problem Language Result Execution time Memory
601194 2022-07-21T12:57:43 Z CSQ31 Uplifting Excursion (BOI22_vault) C++17
20 / 100
 1333 ms 16036 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
ll A[5000],B[5000];
unordered_map<ll,ll>val;
ll dp[2000001];
int main()
{
	int m;
	ll L;
	cin>>m>>L;
	for(int i=-m;i<=m;i++)cin>>A[i+m];
	ll ans = A[m];
	/*
	//subtask 2 m^4 knapsack??
	//consider left and right side separately
	//let ai be number of art piece i chosen
	//1)atleast one of ai , a_{-i} must be 0
	//2)consider only positive
	//ai aj i<j
	//if aj >= i and ai <= Ai-j
	//do ai+=j aj-=i
	//j > i
	//ai <= Ai-M and aj >= M cant be both true
	//a prefix p has ai>Ai-M then p+1 can be anything
	//ahhhhhhhhh iterate first i such that ai <= M
	for(int i=1;i<=m;i++){
	}
	*/
	ll shift = 500500;
	if(L > shift || L < -shift){
		cout<<"impossible"<<'\n';
		return 0;
	}
	for(int i=0;i<=2000000;i++)dp[i] = -1;
	dp[shift] = 0;
	for(ll i=-m;i<=m;i++){
		if(i==0)continue;
		ll z = 1;
		vector<ll>item;
		while(A[i+m]>=z){
			item.push_back(z);
			A[i+m]-=z;
			z*=2;
		}
		if(A[i+m])item.push_back(A[i+m]);
		if(i < 0){
			for(ll x:item){
				for(ll j=-shift-x*i;j<=shift;j++){
					if(dp[j+shift] != -1)dp[j + x*i+shift] = max(dp[j + x*i+shift],dp[j+shift] + x);
				}
			}
		}else{
			for(ll x:item){
				for(ll j=shift-x*i;j>=-shift;j--){
					if(dp[j+shift] != -1)dp[j + x*i+shift] = max(dp[j + x*i+shift],dp[j+shift] + x);
				}
			}			
			
		}
	}
	if(dp[L+shift] == -1){
		cout<<"impossible"<<'\n';
		return 0;
	}
	ans+=dp[L+shift];
	cout<<ans<<'\n';
	
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 10 ms 15868 KB Output is correct
3 Correct 8 ms 15860 KB Output is correct
4 Correct 27 ms 15848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 359 ms 15940 KB Output is correct
7 Correct 162 ms 15844 KB Output is correct
8 Correct 363 ms 15956 KB Output is correct
9 Correct 452 ms 15828 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 20 ms 15872 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 10 ms 15868 KB Output is correct
3 Correct 8 ms 15860 KB Output is correct
4 Correct 27 ms 15848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 359 ms 15940 KB Output is correct
7 Correct 162 ms 15844 KB Output is correct
8 Correct 363 ms 15956 KB Output is correct
9 Correct 452 ms 15828 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 20 ms 15872 KB Output is correct
12 Correct 18 ms 15956 KB Output is correct
13 Correct 11 ms 15956 KB Output is correct
14 Correct 10 ms 15956 KB Output is correct
15 Correct 28 ms 15960 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 396 ms 15956 KB Output is correct
18 Correct 182 ms 15956 KB Output is correct
19 Correct 360 ms 15956 KB Output is correct
20 Correct 484 ms 15948 KB Output is correct
21 Correct 15 ms 15960 KB Output is correct
22 Correct 21 ms 15968 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 937 ms 15936 KB Output is correct
25 Correct 349 ms 15940 KB Output is correct
26 Correct 1333 ms 16036 KB Output is correct
27 Correct 1194 ms 15956 KB Output is correct
28 Correct 21 ms 15968 KB Output is correct
29 Correct 26 ms 15952 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15944 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15944 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15944 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 10 ms 15868 KB Output is correct
3 Correct 8 ms 15860 KB Output is correct
4 Correct 27 ms 15848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 359 ms 15940 KB Output is correct
7 Correct 162 ms 15844 KB Output is correct
8 Correct 363 ms 15956 KB Output is correct
9 Correct 452 ms 15828 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 20 ms 15872 KB Output is correct
12 Correct 39 ms 15944 KB Output is correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15944 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 10 ms 15868 KB Output is correct
3 Correct 8 ms 15860 KB Output is correct
4 Correct 27 ms 15848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 359 ms 15940 KB Output is correct
7 Correct 162 ms 15844 KB Output is correct
8 Correct 363 ms 15956 KB Output is correct
9 Correct 452 ms 15828 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 20 ms 15872 KB Output is correct
12 Correct 18 ms 15956 KB Output is correct
13 Correct 11 ms 15956 KB Output is correct
14 Correct 10 ms 15956 KB Output is correct
15 Correct 28 ms 15960 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 396 ms 15956 KB Output is correct
18 Correct 182 ms 15956 KB Output is correct
19 Correct 360 ms 15956 KB Output is correct
20 Correct 484 ms 15948 KB Output is correct
21 Correct 15 ms 15960 KB Output is correct
22 Correct 21 ms 15968 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 937 ms 15936 KB Output is correct
25 Correct 349 ms 15940 KB Output is correct
26 Correct 1333 ms 16036 KB Output is correct
27 Correct 1194 ms 15956 KB Output is correct
28 Correct 21 ms 15968 KB Output is correct
29 Correct 26 ms 15952 KB Output is correct
30 Correct 39 ms 15944 KB Output is correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15944 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 10 ms 15868 KB Output is correct
3 Correct 8 ms 15860 KB Output is correct
4 Correct 27 ms 15848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 359 ms 15940 KB Output is correct
7 Correct 162 ms 15844 KB Output is correct
8 Correct 363 ms 15956 KB Output is correct
9 Correct 452 ms 15828 KB Output is correct
10 Correct 16 ms 15956 KB Output is correct
11 Correct 20 ms 15872 KB Output is correct
12 Correct 18 ms 15956 KB Output is correct
13 Correct 11 ms 15956 KB Output is correct
14 Correct 10 ms 15956 KB Output is correct
15 Correct 28 ms 15960 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 396 ms 15956 KB Output is correct
18 Correct 182 ms 15956 KB Output is correct
19 Correct 360 ms 15956 KB Output is correct
20 Correct 484 ms 15948 KB Output is correct
21 Correct 15 ms 15960 KB Output is correct
22 Correct 21 ms 15968 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 937 ms 15936 KB Output is correct
25 Correct 349 ms 15940 KB Output is correct
26 Correct 1333 ms 16036 KB Output is correct
27 Correct 1194 ms 15956 KB Output is correct
28 Correct 21 ms 15968 KB Output is correct
29 Correct 26 ms 15952 KB Output is correct
30 Correct 39 ms 15944 KB Output is correct
31 Incorrect 0 ms 212 KB Output isn't correct
32 Halted 0 ms 0 KB -