Submission #600399

#	Time	Username	Problem	Language	Result	Execution time	Memory
600399		flappybird	Uplifting Excursion (BOI22_vault)	C++17	50 / 100	2591 ms	8992 KiB

vault

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 303030
#define MAXS 19
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define smin(a, x) (a)=(min((a), (x)))
ll arr[MAX];
ll dp[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int M;
	ll L;
	cin >> M >> L;
	int i;
	ll A, B;
	A = B = 0;
	for (i = -M; i <= M; i++) cin >> arr[i + M], (i < 0 ? A : B) += arr[i + M] * i;
	if (B < L || A > L) {
		cout << "impossible" << ln;
		return 0;
	}
	if (A + B <= L) reverse(arr, arr + M + M + 1), L *= -1, swap(A, B), A *= -1, B *= -1;
	ll cnt = 0;
	if (A + B == L) {
		for (i = -M; i <= M; i++) cnt += arr[i + M];
		cout << cnt << ln;
		return 0;
	}
	for (i = -M; i < 0; i++) cnt += arr[i + M];
	ll c = 0;
	for (i = 1; i <= M; i++) {
		if (A + arr[i + M] * i > L) {
			ll x = (L - A) / i;
			if (x) c = x;
			A += x * i;
			cnt += x;
			break;
		}
		else A += arr[i + M] * i, cnt += arr[i + M];
	}
	int e = i;
	A = L - A;
	vector<tuple<ll, ll, ll>> lst;
	for (i = -M; i < 0; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
	lst.emplace_back(e, -1, arr[e + M] - c);
	for (i = e + 1; i <= M; i++) if (arr[i + M]) lst.emplace_back(i, -1, arr[i + M]);
	for (i = 1; i < e; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
	if (c) lst.emplace_back(-e, 1, c);
	fill(dp, dp + 303000, INF);
	int bias = M * M + 20;
	dp[bias] = 0;
	for (auto& [w, v, mx] : lst) {
		int ww = abs(w);
		vector<priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>> vpq(ww);
		if (w < 0) {
			for (i = M * M + 10; i >= -M * M - 10; i--) {
				int ind = (i % ww + ww) % ww;
				while (vpq[ind].size() && vpq[ind].top().second > i + M * mx) vpq[ind].pop();
				ll pv = dp[i + bias];
				if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first - v * (i / ww));
				vpq[ind].emplace(pv + v * (i / ww), i);
			}
		}
		else {
			for (i = -M * M - 10; i <= M * M + 10; i++) {
				int ind = (i % ww + ww) % ww;
				while (vpq[ind].size() && vpq[ind].top().second < i - M * mx) vpq[ind].pop();
				ll pv = dp[i + bias];
				if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first + v * (i / ww));
				vpq[ind].emplace(pv - v * (i / ww), i);
			}
		}
	}
	if (dp[bias + A] > 50 * M) cout << "impossible" << ln;
	else cout << cnt + arr[M] - dp[bias + A];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 0 / 10