Submission #99712

#	Time	Username	Problem	Language	Result	Execution time	Memory
99712		YaDon4ick	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	258 ms	512 KiB

sculpture

//By Don4ick 
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qewr1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 2005;
const int M = 105;
const int LOG = 50;

using namespace std;

int n, a, b, dp[N];
ll p[N];
bool was[M][M];

void solve1()
{
	ll ban = 0, ans = 0;
	for (int i = LOG - 1; i >= 0; i--)
	{
		ban |= (1ll << i);
		memset(was, false, sizeof(was));
		was[0][0] = true;
		forn(j, n)
		{
			for (int k = 1; k <= j; k++)
			{
				for (int f = 1; f <= j; f++)
				{	
					if (!(ban & (p[j] - p[f - 1])))
						was[j][k] |= was[f - 1][k - 1];
				}
			}
		}
		bool found = false;
		for (int j = a; j <= b; j++)
			if (was[n][j])
				found = true;
		if (!found)
			ban ^= (1ll << i), ans ^= (1ll << i);
	}                                            
	cout << ans << endl;
}	

void solve2()
{
	ll ban = 0, ans = 0;
	for (int i = LOG - 1; i >= 0; i--)
	{	
		ban |= (1ll << i);
		fill(dp + 1, dp + n + 1, n + 1);
		dp[0] = 0;
		for (int j = 1; j <= n; j++)
		{	
			for (int k = 1; k <= n; k++)
			{
				if (!(ban & (p[j] - p[k - 1])))
					dp[j] = min(dp[j], dp[k - 1] + 1);
			}
		}
		if (dp[n] > b)
			ban ^= (1ll << i), ans |= (1ll << i);
	}
	cout << ans << endl;
}

int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie();
	//cout.tie();		

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	//~read
	cin >> n >> a >> b;
	forn(i, n)
		cin >> p[i];
	//~pref_sum
	forn(i, n)
		p[i] += p[i - 1];
	//~solve
	if (n <= 100)	
		solve1();
	else
		solve2();

	return 0;
}

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