Submission #600306

#	Time	Username	Problem	Language	Result	Execution time	Memory
600306		flappybird	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	4 ms	1504 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];
int 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];
	int c = 0;
	for (i = 1; i <= M; i++) {
		if (A + arr[i + M] * i > L) {
			ll x = (L - A) / i;
			if (x) c = 1;
			A += x * i;
			cnt += x;
			break;
		}
		else A += arr[i + M] * i, cnt += arr[i + M];
	}
	int e = i;
	A = L - A;
	vector<pii> v;
	for (i = -M; i < 0; i++) if (arr[i + M]) v.emplace_back(-i, 1);
	for (i = e; i <= M; i++) if (arr[i + M]) v.emplace_back(i, -1);
	if (!c) e--;
	for (i = 1; i <= e; i++) if (arr[i + M]) v.emplace_back(-i, 1);
	fill(dp, dp + 303000, M * 10);
	int bias = M * M + 20;
	dp[bias] = 0;
	for (auto& [w, v] : v) {
		if (w < 0) for (i = -M * M - 10 - w; i <= M * M + 10; i++) dp[i + w + bias] = min(dp[i + w + bias], dp[i + bias] + v);
		else for (i = M * M + 10 - w; i >= -M * M - 10; i--) dp[i + w + bias] = min(dp[i + w + bias], dp[i + bias] + v);
	}
	if (dp[bias + A] > 5 * M) cout << "impossible" << ln;
	else cout << cnt + arr[M] - dp[bias + A];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 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