oj.uz

Submission #594027

# Submission time Handle Problem Language Result Execution time Memory
594027 2022-07-11T22:42:39 Z CaroLinda Uplifting Excursion (BOI22_vault) C++14
20 / 100
 4946 ms 4300 KB 
#include <bits/stdc++.h>

#define ll long long

const ll inf = 1e18+10LL;
const int MAX = 505005;

using namespace std;

int M;
int dp[2*MAX];
int qtd[MAX*2];
ll L;

// -----------
int l, r;
deque<pair<int,int> > dq;

void initialize(){
	l = 1, r = 0;
	while(!dq.empty())
		dq.pop_back();
}

void insere(int val){
	while(!dq.empty() && dq.back().first <= val)
		dq.pop_back();

	dq.push_back(make_pair(val, ++r));
}

void popa(){
	if(dq.front().second == l++)
		dq.pop_front();
}

int qry(){
	if(dq.empty())return 0;
	return dq.front().first;
}
// -----------

void makeNegative(int qtd, int val){
	val = -val;

	for(int i = 0; i < val; i++){
		int R = i-val;
		int L = i;

		initialize();

		for(int j = i; j < 2*MAX; j += val){
			while(R+val < 2*MAX && ((R-j)/val) < qtd ){
				R += val;
				insere(dp[R]+R/val);
			}
			while(L < j){
				L += val;
				popa();
			}

			dp[j] = qry()-j/val;
		}
	}

}

void makePositive(int qtd, int val){
	for(int i = 2*MAX-1; i >= 2*MAX-val; i--){
		initialize();
		int L = i+val, R = i;

		for(int j = i; j >= 0; j -= val){
			while(L-val >= 0 && (j-L)/val < qtd){
				L -= val;
				insere(dp[L]-L/val);
			}
			while(R > j){
				R -= val;
				popa();
			}

			dp[j] = qry() + j/val;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> M >> L;	
	if( L+MAX >= 2LL*MAX || L+MAX < 0 ){
		cout << "impossible\n";
		return 0;
	}

	for(int i = 0; i < MAX*2; i++){
		dp[i] = -2*MAX;
	}

	dp[MAX] = 0;

	for(int i = -M; i <= M; i++){
		cin >> qtd[i+M];
	}

	for(int i = -M; i < 0; i++){
		if(qtd[i+M])
			makeNegative(qtd[i+M],i);
		if(qtd[M-i])
			makePositive(qtd[M-i],-i);
	}

	for(int i = 0; i < 2*MAX; i++)
		dp[i] += qtd[M];

	if(dp[L+MAX] < 0)
		cout << "impossible\n";
	else cout << dp[L+MAX] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4276 KB Output is correct
2 Correct 77 ms 4264 KB Output is correct
3 Correct 28 ms 4280 KB Output is correct
4 Correct 195 ms 4260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2448 ms 4268 KB Output is correct
7 Correct 1081 ms 4260 KB Output is correct
8 Correct 2428 ms 4256 KB Output is correct
9 Correct 2509 ms 4264 KB Output is correct
10 Correct 52 ms 4180 KB Output is correct
11 Correct 120 ms 4256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4276 KB Output is correct
2 Correct 77 ms 4264 KB Output is correct
3 Correct 28 ms 4280 KB Output is correct
4 Correct 195 ms 4260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2448 ms 4268 KB Output is correct
7 Correct 1081 ms 4260 KB Output is correct
8 Correct 2428 ms 4256 KB Output is correct
9 Correct 2509 ms 4264 KB Output is correct
10 Correct 52 ms 4180 KB Output is correct
11 Correct 120 ms 4256 KB Output is correct
12 Correct 102 ms 4264 KB Output is correct
13 Correct 76 ms 4264 KB Output is correct
14 Correct 28 ms 4180 KB Output is correct
15 Correct 209 ms 4260 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2421 ms 4260 KB Output is correct
18 Correct 1084 ms 4260 KB Output is correct
19 Correct 2395 ms 4256 KB Output is correct
20 Correct 2501 ms 4260 KB Output is correct
21 Correct 53 ms 4180 KB Output is correct
22 Correct 129 ms 4260 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 4827 ms 4260 KB Output is correct
25 Correct 1902 ms 4268 KB Output is correct
26 Correct 4946 ms 4264 KB Output is correct
27 Correct 4921 ms 4300 KB Output is correct
28 Correct 56 ms 4276 KB Output is correct
29 Correct 120 ms 4180 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 4180 KB Output is correct
2 Incorrect 1 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 201 ms 4180 KB Output is correct
2 Incorrect 1 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 201 ms 4180 KB Output is correct
2 Incorrect 1 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 101 ms 4276 KB Output is correct
2 Correct 77 ms 4264 KB Output is correct
3 Correct 28 ms 4280 KB Output is correct
4 Correct 195 ms 4260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2448 ms 4268 KB Output is correct
7 Correct 1081 ms 4260 KB Output is correct
8 Correct 2428 ms 4256 KB Output is correct
9 Correct 2509 ms 4264 KB Output is correct
10 Correct 52 ms 4180 KB Output is correct
11 Correct 120 ms 4256 KB Output is correct
12 Correct 201 ms 4180 KB Output is correct
13 Incorrect 1 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 201 ms 4180 KB Output is correct
2 Incorrect 1 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 101 ms 4276 KB Output is correct
2 Correct 77 ms 4264 KB Output is correct
3 Correct 28 ms 4280 KB Output is correct
4 Correct 195 ms 4260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2448 ms 4268 KB Output is correct
7 Correct 1081 ms 4260 KB Output is correct
8 Correct 2428 ms 4256 KB Output is correct
9 Correct 2509 ms 4264 KB Output is correct
10 Correct 52 ms 4180 KB Output is correct
11 Correct 120 ms 4256 KB Output is correct
12 Correct 102 ms 4264 KB Output is correct
13 Correct 76 ms 4264 KB Output is correct
14 Correct 28 ms 4180 KB Output is correct
15 Correct 209 ms 4260 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2421 ms 4260 KB Output is correct
18 Correct 1084 ms 4260 KB Output is correct
19 Correct 2395 ms 4256 KB Output is correct
20 Correct 2501 ms 4260 KB Output is correct
21 Correct 53 ms 4180 KB Output is correct
22 Correct 129 ms 4260 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 4827 ms 4260 KB Output is correct
25 Correct 1902 ms 4268 KB Output is correct
26 Correct 4946 ms 4264 KB Output is correct
27 Correct 4921 ms 4300 KB Output is correct
28 Correct 56 ms 4276 KB Output is correct
29 Correct 120 ms 4180 KB Output is correct
30 Correct 201 ms 4180 KB Output is correct
31 Incorrect 1 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 201 ms 4180 KB Output is correct
2 Incorrect 1 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 101 ms 4276 KB Output is correct
2 Correct 77 ms 4264 KB Output is correct
3 Correct 28 ms 4280 KB Output is correct
4 Correct 195 ms 4260 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2448 ms 4268 KB Output is correct
7 Correct 1081 ms 4260 KB Output is correct
8 Correct 2428 ms 4256 KB Output is correct
9 Correct 2509 ms 4264 KB Output is correct
10 Correct 52 ms 4180 KB Output is correct
11 Correct 120 ms 4256 KB Output is correct
12 Correct 102 ms 4264 KB Output is correct
13 Correct 76 ms 4264 KB Output is correct
14 Correct 28 ms 4180 KB Output is correct
15 Correct 209 ms 4260 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2421 ms 4260 KB Output is correct
18 Correct 1084 ms 4260 KB Output is correct
19 Correct 2395 ms 4256 KB Output is correct
20 Correct 2501 ms 4260 KB Output is correct
21 Correct 53 ms 4180 KB Output is correct
22 Correct 129 ms 4260 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 4827 ms 4260 KB Output is correct
25 Correct 1902 ms 4268 KB Output is correct
26 Correct 4946 ms 4264 KB Output is correct
27 Correct 4921 ms 4300 KB Output is correct
28 Correct 56 ms 4276 KB Output is correct
29 Correct 120 ms 4180 KB Output is correct
30 Correct 201 ms 4180 KB Output is correct
31 Incorrect 1 ms 212 KB Output isn't correct
32 Halted 0 ms 0 KB -