Submission #592188

#	Time	Username	Problem	Language	Result	Execution time	Memory
592188		tutis	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	922 ms	64180 KiB

vault

/*input
1 5
0 0 6

*/

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T,  null_type,  less<T>,  rb_tree_tag,  tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(0);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll M;
	ll L;
	cin >> M >> L;
	ll A_[2 * M + 1];
	ll* A = A_ + M;
	for (ll i = -M; i <= M; i++)
		cin >> A[i];
	L = -L;
	ll cnt = 0;
	for (ll l = -M; l <= M; l++)
	{
		L += l * A[l];
		cnt += A[l];
	}
	A[0] = 0;
	ld L_ = L;
	ld C_[2 * M + 1];
	ld* C = C_ + M;
	C[0] = 0;
	ll sum[M + 2];
	for (ll x = M; x >= 1; x--)
	{
		for (ll v : {x, -x})
		{
			C[v] = L_ / v;
			C[v] = max(ld(0), C[v]);
			C[v] = min(ld(A[v]), C[v]);
			L_ -= C[v] * v;
		}
		sum[x] = (ll)roundl(L_);
	}
	sum[0] = 0;
	sum[M + 1] = L;
	const ll mxdel = 40000;
	ll infi = 2e18;
	ll ej[M + 2][2 * mxdel + 1];
	for (ll a = 0; a <= M + 1; a++)
		for (ll b = 0; b <= 2 * mxdel; b++)
			ej[a][b] = infi;
	ej[M + 1][0 + mxdel] = 0;
	for (ll x = M; x >= 0; x--)
	{
		for (ll a = -mxdel; a <= mxdel; a++)
		{
			ll val = sum[x + 1] + a - sum[x];
			ll val1 = sum[x + 1] + a - sum[x] + mxdel;
			ll e = ej[x + 1][a + mxdel];
			if (e == infi)
				continue;
			//val1 - k * v=0
			// - k * v=val1
			//val1 - k * v=mxdel*2
			ll v1 = (x == 0) ? 0 : -(val1 / x);
			ll v2 = (x == 0) ? 0 : ((mxdel * 2 - val1) / x);
			for (ll v : {x, -x})
			{
				ll opt = 0;
				if (x != 0)
					opt = val / v;
				opt = max(opt, 0ll);
				opt = min(opt, A[v]);
				ll lo = 0;
				ll hi = A[v];
				if (v > 0)
				{
					lo = max(lo, v1);
					hi = min(hi, v2);
				}
				else
				{
					lo = max(lo, -v2);
					hi = min(hi, -v1);
				}
				for (ll k = max(lo, opt - x - 5); k <= min(hi, opt + x + 5); k++)
				{
					ll val_ = val1 - k * v;
					ll e_ = e + k;
					if (0 <= val_ && val_ <= mxdel * 2)
					{
						if (e_ < ej[x][val_])
						{
							ej[x][val_] = e_;
						}
					}
				}
			}
		}
	}
	ll best = ej[0][mxdel];
	if (best != infi)
		cout << cnt - best << "\n";
	else
		cout << "impossible\n";
}

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