Submission #592226

#	Time	Username	Problem	Language	Result	Execution time	Memory
592226		tutis	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	94 ms	3468 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);
const int mxdel = 100000;
ll A_[2 * 300 + 1];
ll ej[2][2 * mxdel + 1];
ll sum[300 + 2];
ll C_[2 * 300 + 1];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int M;
	ll L;
	cin >> M >> L;
	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;
	ll L_ = L;
	ll* C = C_ + M;
	C[0] = 0;
	for (ll x = M; x >= 1; x--)
	{
		for (ll v : {x, -x})
		{
			C[v] = L_ / v;
			C[v] = max(ll(0), C[v]);
			C[v] = min(ll(A[v]), C[v]);
			L_ -= C[v] * v;
		}
		sum[x] = (ll)roundl(L_);
	}
	sum[0] = 0;
	sum[M + 1] = L;
	ll infi = 2e18;
	for (ll b = 0; b <= 2 * mxdel; b++)
		ej[(M + 1) % 2][b] = infi;
	ej[(M + 1) % 2][0 + mxdel] = 0;
	for (int x = M; x >= 0; x--)
	{
		int x1 = (x + 1) % 2;
		int x0 = x % 2;
		for (int b = 0; b <= 2 * mxdel; b++)
			ej[x0][b] = infi;
		for (int a = -mxdel; a <= mxdel; a++)
		{
			ll val = sum[x + 1] + a - sum[x];
			ll e = ej[x1][a + mxdel];
			if (e != infi)
				for (ll v : {x, -x})
				{
					ll opt = 0;
					if (x != 0)
						opt = val / v;
					opt = max(opt, 0ll);
					opt = min(opt, A[v]);
					for (ll k = max(0ll, opt - x); k <= min(A[v], opt); k++)
					{
						ll val_ = val - k * v;
						ll e_ = e + k;
						if (abs(val_) <= mxdel)
						{
							if (e_ < ej[x0][val_ + mxdel])
							{
								ej[x0][val_ + mxdel] = e_;
							}
						}
					}
				}
		}
	}
	ll best = ej[0][mxdel];
	if (best != infi)
		cout << cnt - best << "\n";
	else
		cout << "impossible\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