Submission #854666

#	Time	Username	Problem	Language	Result	Execution time	Memory
854666		parsadox2	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	65 ms	612 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5 , M = 1e2 + 10;
int n , A , B , ar[N];
long long ps[N];

long long solve1()
{
	int dp[N];
	long long ans = 0;
	for(int bit = 41 ; bit > -1 ; bit--)
	{
		long long now = (1LL << bit);
		dp[0] = 0;
		for(int i = 1 ; i <= n ; i++)
		{
			dp[i] = N;
			for(int j = 0 ; j < i ; j++)
			{
				long long sum = ps[i] - ps[j];
				sum = sum - (sum & ans);
				if(sum >= now)
					continue;
				dp[i] = min(dp[i] , dp[j] + 1);
			}
		}
		if(dp[n] > B)
			ans |= now;
	}
	return ans;
}

long long solve2()
{
	bool dp[M][M];
	long long ans = 0;
	for(int bit = 40 ; bit > -1 ; bit--)
	{
		memset(dp , false , sizeof dp);
		long long now = (1LL << bit);
		dp[0][0] = true;
		for(int i = 1 ; i <= n ; i++)  for(int j = 1 ; j <= B ; j++)  for(int k = 0 ; k < i ; k++)
		{
			long long sum = ps[i] - ps[k];
			sum = sum - (sum & ans);
			if(sum >= now || !dp[k][j - 1])
				continue;
			dp[i][j] = true;
			//cout << i << " : " << j << " " << k << endl;
			break;
		}
		bool ok = false;
		for(int i = A ; i <= B ; i++)  if(dp[n][i])
			ok = true;
		if(!ok)
			ans |= now;
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(false);
	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++)
		ps[i] = ar[i] + ps[i - 1];

	if(A == 1)
		cout << solve1() << '\n';
	else
		cout << solve2() << '\n';
	return 0;
}

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