Submission #1187807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187807		tamyte	Uplifting Excursion (BOI22_vault)	C++20	0 / 100	111 ms	2024 KiB

vault

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


unordered_map<int, ll> take, not_take;
unordered_map<int, ll> dp, ndp;
ll low = -100 * 100, high = 100 * 100;
const ll LINF = -2e18;



void add(ll v, ll d) {
	ndp = dp;
	for (int i = low; i <= high; ++i) {
		if (low <= i - v * d && i - v * d <= high) {
			dp[i] = max(dp[i], ndp[i - v * d] + v);
		}
	}
	for (int i = low; i <= high; ++i) {
		dp[i] = (dp[i] <= LINF + high ? LINF : dp[i]);
	}
}
void sub(ll v, ll d) {
	ndp = dp;
	for (int i = low; i <= high; ++i) {
		if (low <= i + v * d && i + v * d <= high) {
			dp[i] = max(dp[i], ndp[i + v * d] - v);
		}
	}
	for (int i = low; i <= high; ++i) {
		dp[i] = (dp[i] <= LINF + high ? 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;
		// if (now > 0) cout << now << " : " << i << endl;
	}
	// cout << "DONE!" << endl;
	// cout << sum << " " << res << endl;
	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 (now > 0) cout << now << " : " << i << endl;
	}
	// cout << sum << " " << res << endl;
	if (sum + high < L) {
		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;
		}
	}
	// cout << sum << " " << res << endl;
	for (int i = low; i <= high; ++i) {
		dp[i] = ndp[i] = LINF;
	}
	dp[0] = ndp[0] = 0;
	for (int i = -m ; i <= m; ++i) {
		if (i == 0) continue;
		ll k, s;
		s = 0;
		// cout << dp.size() << " " << ndp.size() << endl;
		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]);
		// if (i >= 47) {
			// cout << "i = " << i << ", K = " << k << "\n";
		// }
		for (ll j = 0; s + (1 << j) <= k; s += (1 << j), ++j) {
			sub((1 << j), i);
		}
		sub(k - s, i);
	}
	// for (int i = -50; i <= 50; ++i) {
		// cout << i << " = " << dp[i] << endl;
	// }
	// cout << endl;
	// cout << L - sum << " = " << dp[L - sum] << endl;
	if (!dp.count(L - sum) || dp[L - sum] < 0) {
		cout << "impossible\n";
	} else {
		cout << res + dp[L - sum] << "\n";
	}
}

• 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