Submission #705933

#TimeUsernameProblemLanguageResultExecution timeMemory
705933600MihneaBali Sculptures (APIO15_sculpture)C++17
71 / 100
1089 ms2508 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 7;
int n;
int minpart;
int maxpart;
long long pref[N];

long long getsum(int l, int r)
{
	assert(1 <= l && l <= r && r <= n);
	return pref[r] - pref[l - 1];
}

bool ok[N][N];
bool is[N][N];

bool isok(long long hasnot)
{
	for (int l = 1; l <= n; l++)
		for (int r = l; r <= n; r++)
		{
			ok[l][r] = 1;
			if (getsum(l, r) & hasnot)
				ok[l][r] = 0;
		}	
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			is[i][j] = 0;
	is[0][0] = 1;
	for (int r = 1; r <= n; r++)
		for (int l = 1; l <= r; l++)
			for (int cnt = 1; cnt <= n; cnt++)
				if (ok[l][r] && is[l - 1][cnt - 1])
					is[r][cnt] = 1;
	for (int i = minpart; i <= maxpart; i++)
		if (is[n][i])
			return 1;
	return 0;
}

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

	cin >> n >> minpart >> maxpart;
	for (int i = 1; i <= n; i++)	
	{
		cin >> pref[i];
		pref[i] += pref[i - 1];
	}
	long long hasnot = 0;
	for (int bit = 60; bit >= 0; bit--)
	{
		if (isok(hasnot + (1LL << bit)))
			hasnot += (1LL << bit);
	}	
	cout << (1LL << 61) - 1 - hasnot << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...