Submission #590676

#	Time	Username	Problem	Language	Result	Execution time	Memory
590676		tutis	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	2488 ms	7116 KiB

vault

/*input
3 5
3 1 0 2 0 0 2
*/

#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;
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];
	for (int i = 0; i <= 2 * M; i++)
		cin >> A[i];
	array<array<pair<ll, ll>, 300>, 301> v;
	for (int m = 1; m <= M; m++)
	{
		for (int k = 0; k < m; k++)
			v[m][k] = { -3e18, -3e18};
		v[m][0] = {0, 0};
	}
	ll ret = -1;
	for (ll i = 1; i <= M; i++)
	{
		A[i + M] -= M;
		if (A[i + M] >= 0)
		{
			auto w = v;
			for (ll m = M / 2 + 1; m <= M; m++)
				for (ll k = 0; k < m; k++)
				{
					ll x = v[m][k].first;
					ll mx = (L - x) / i;
					mx = min(mx, A[i + M]);
					for (ll c = mx; c >= 0 && c >= mx - M; c--)
					{
						ll val = x + i * c;
						ll cnt = v[m][k].second + c;
						for (ll md = M / 2 + 1; md <= M; md++)
						{
							ll vv = val % md;
							w[md][vv] = max(w[md][vv], {val, cnt});
						}
					}
				}
			v = w;
			A[i + M] = M;
		}
		else
			A[i + M] += M;
	}
	int D = 505500;
	vector<int> C(2 * D + 1, -1e9);
	C[D] = 0;
	int del = 0;
	for (int i = 1; i <= M; i++)
	{
		for (int k = 1; k <= A[i + M]; k++)
		{
			for (int j = min(D + del, 2 * D - i); j >= max(0, D - del); j--)
			{
				C[j + i] = max(C[j + i], C[j] + 1);
			}
			del += i;
		}
		for (int k = 1; k <= A[-i + M]; k++)
		{
			for (int j = max(D - del, i); j <= min(D + del, 2 * D); j++)
			{
				C[j - i] = max(C[j - i], C[j] + 1);
			}
			if (k > A[i + M])
				del += i;
		}
	}


	for (int m = 1; m <= M; m++)
		for (int k = 0; k < m; k++)
			if (-D <= L - v[m][k].first && L - v[m][k].first <= D)
				ret = max(ret, C[D + (L - v[m][k].first)] + v[m][k].second);
	if (ret < 0)
		cout << "impossible\n";
	else
		cout << ret + A[M] << "\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