Submission #1187811

#TimeUsernameProblemLanguageResultExecution timeMemory
1187811tamyteUplifting Excursion (BOI22_vault)C++20
100 / 100
1832 ms3320 KiB
#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;
		// 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 + m < 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 = 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;
		// 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;
	int offset = L - sum + N;
	if (offset > 2 * N || offset < 0) {
		cout << "impossible\n";
		return 0;
	}
	if (dp[offset] == LINF) {
		cout << "impossible\n";
		return 0;
	}
	cout << res + dp[offset] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...