Submission #594027

#	Time	Username	Problem	Language	Result	Execution time	Memory
594027		CaroLinda	Uplifting Excursion (BOI22_vault)	C++14	20 / 100	4946 ms	4300 KiB

vault

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10