oj.uz

Submission #594017

# Submission time Handle Problem Language Result Execution time Memory
594017 2022-07-11T22:27:04 Z CaroLinda Uplifting Excursion (BOI22_vault) C++14
0 / 100
 285 ms 1440 KB 
#include <bits/stdc++.h>

#define ll long long

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

using namespace std;

int M;
int dp[2*MAX];
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 >= 2*MAX ){
		cout << "impossible\n";
		return 0;
	}

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

	dp[MAX] = 0;

	for(int i = -M, qtd; i <= M; i++){
		cin >> qtd;
		if(qtd == 0) continue;
		if(i < 0) makeNegative(qtd,i);
		else if(i > 0) makePositive(qtd,i);
		else{
			for(int i = 0; i < 2*MAX; i++)
				dp[i] += qtd;
		}
	}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 24 ms 820 KB Output is correct
5 Runtime error 285 ms 1440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 24 ms 820 KB Output is correct
5 Runtime error 285 ms 1440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 724 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 25 ms 724 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 25 ms 724 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 12 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 24 ms 820 KB Output is correct
5 Runtime error 285 ms 1440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 724 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 12 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 24 ms 820 KB Output is correct
5 Runtime error 285 ms 1440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 724 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 12 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 24 ms 820 KB Output is correct
5 Runtime error 285 ms 1440 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -