제출 #1187823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187823		tamyte	Uplifting Excursion (BOI22_vault)	C++20	50 / 100	1105 ms	3316 KiB

vault

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


unordered_map<int, ll> take, not_take;
int N = 300 * 300;
const ll LINF = -2e18;
vector<ll> dp(2 * N + 1, LINF), ndp(2 * N + 1, LINF);



void add(ll v, ll d) {
	ndp = dp;
	for (int i = 0; i <= 2 * N; ++i) {
		if (0 <= i - v * d && i - v * d <= 2 * N) {
			dp[i] = max(dp[i], ndp[i - v * d] + v);
		}
	}
	for (int i = 0; i <= 2 * N; ++i) {
		dp[i] = (dp[i] <= LINF + N ? LINF : dp[i]);
	}
}
void sub(ll v, ll d) {
	ndp = dp;
	for (int i = 0; i <= 2 * N; ++i) {
		if (0 <= i + v * d && i + v * d <= 2 * N) {
			dp[i] = max(dp[i], ndp[i + v * d] - v);
		}
	}
	for (int i = 0; i <= 2 * N; ++i) {
		dp[i] = (dp[i] <= LINF + N ? LINF : dp[i]);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m;
	ll L;
	cin >> m >> L;
	ll res = 0;
	for (int i = -m; i <= m; ++i) {
		cin >> not_take[i];
	}
	if (L < 0) {
		for (int i = -m; i <= 0; ++i) {
			swap(not_take[i], not_take[-i]);
		}
		L = -L;
	}
	ll sum = 0;
	for (int i = -m; i <= 0; ++i) {
		ll now = not_take[i];
		sum += now * i;
		not_take[i] -= now;
		take[i] += now;
		res += now;
	}
	for (int i = 1; i <= m; ++i) {
		ll now = min(not_take[i], (L - sum) / i);
		sum += now * i;
		not_take[i] -= now;
		take[i] += now;
		res += now;
	}
	if (L - sum > m * m) { // max take all i = m and m * m times?
		for (int i = -m; i < 0; ++i) {
			ll now = min(take[i], (L - sum) / (-i));
			sum -= now * i;
			take[i] -= now;
			not_take[i] += now;
			res -= now;
		}
	}
	// assert(sum <= L);
	for (int i = 0; i <= 2 * N; ++i) {
		dp[i] = ndp[i] = LINF;
	}
	dp[N] = ndp[N] = 0;
	for (int i = -m ; i <= m; ++i) {
		if (i == 0) continue;
		ll k, s;
		s = 0;
		k = min((ll)m, not_take[i]);
		for (ll j = 0; s + (1 << j) <= k; s += (1 << j), ++j) {
			add((1 << j), i);
		}
		add(k - s, i);
		s = 0;
		k = min((ll)m, take[i]);
		for (ll j = 0; s + (1 << j) <= k; s += (1 << j), ++j) {
			sub((1 << j), i);
		}
		sub(k - s, i);
	}
	int offset = L - sum + N;
	assert(offset <= 2 * N);
	assert(offset >= 0);
	if (dp[offset] == LINF) {
		cout << "impossible\n";
		return 0;
	}
	cout << res + dp[offset] << "\n";
}

• 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