Submission #705939

#	Time	Username	Problem	Language	Result	Execution time	Memory
705939		600Mihnea	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	332 ms	4308 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 7;
const int INF = (int) 1e9 + 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];
int dp[N];

bool isok(long long hasnot)
{
	if (minpart > 1)
	{
		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;
	}
	for (int i = 0; i <= n; i++)
		dp[i] = INF;
	dp[0] = 0;
	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 r = 1; r <= n; r++)
		for (int l = 1; l <= r; l++)
			if (ok[l][r])
				dp[r] = min(dp[r], dp[l - 1] + 1);
	return dp[n] <= maxpart;
}

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;
}

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