Submission #336931

#	Time	Username	Problem	Language	Result	Execution time	Memory
336931		Drew_	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	246 ms	1192 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")


#define ll long long

int const N = 2007;
ll const inf = (1LL << 60) - 1;

int n, a, b;
ll ar[N];
ll pfx[N];

class solutionA1
{
public:

	ll dp[N]; //[idx] = {minimum group}
	bool check(ll val)
	{
		fill(dp, dp+N, inf);
		dp[0] = 0;

		for (int i = 1; i <= n; ++i)
		{
			for (int j = i-1; j >= 0; --j)
			{
				ll sum = pfx[i] - pfx[j];
				if ((sum | val) == val)
					dp[i] = min(dp[i], 1 + dp[j]);
			}
		}

		return dp[n] <= b;
	}

	void solve()
	{
		ll ans = inf;
		for (int i = 59; i >= 0; --i)
		{
			if (check(ans ^ (1LL << i)))
				ans ^= (1LL << i);
		}
		cout << ans << '\n';
	}
};

class solutionGeneral
{
public:

	//bool dp[N][N]; //[idx][group] = {bool}
	//unable to use array for some reason
	bool check(ll val)
	{
		vector<vector<bool>> dp(N, vector<bool> (N, false));

		dp[0][0] = true;
		for (int i = 1; i <= n; ++i) //idx
		{
			for (int j = 1; j <= n; ++j) //group
			{
				for (int k = i-1; k >= 0; --k)
				{
					ll sum = pfx[i] - pfx[k];
					if ((sum | val) == val)
						dp[i][j] = (dp[i][j] || dp[k][j-1]);
				}
			}
		}

		for (int i = a; i <= b; ++i)
			if (dp[n][i])
				return true;

		return false;
	}
	
	void solve()
	{
		ll ans = inf;
		for (int i = 59; i >= 0; --i)
		{
			if (check(ans ^ (1LL << i)))
				ans ^= (1LL << i);
		}
		cout << ans << '\n';
	}
};

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> a >> b;
	for (int i = 1; i <= n; ++i)
		cin >> ar[i];

	for (int i = 1; i <= n; ++i)
		pfx[i] = ar[i] + pfx[i-1];


	if (a == 1)
	{
		solutionA1 obj;
		obj.solve();
	}
	else
	{
		solutionGeneral obj;
		obj.solve();
	}

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29