Submission #46589

#	Time	Username	Problem	Language	Result	Execution time	Memory
46589		Mahdi_Jfri	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	178 ms	868 KiB

sculpture

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

#define ll long long
#define pb push_back

const int maxn = 2e3 + 20;
const ll inf = (1LL << 51) - 1;
const int shit = 1e2 + 20;

int a[maxn] , dp[maxn] , n , _ , b;

bool pd[shit][shit];

int f(ll m)
{
	for(int i = 1; i <= n; i++)
	{
		dp[i] = 1e9;
		ll sum = 0;

		for(int j = i - 1; j >= 0; j--)
		{
			sum += a[j + 1];

			if((sum | m) == m)
				dp[i] = min(dp[i] , dp[j] + 1);
		}
	}

	return dp[n];

}

bool f2(ll m)
{
	memset(pd , 0 , sizeof pd);
	pd[0][0] = 1;

	for(int i = 1; i <= n; i++)
	{
		for(int k = 1; k <= i; k++)
		{
			ll sum = 0;
			for(int j = i - 1; j >= 0; j--)
			{
				sum += a[j + 1];
	
				if((sum | m) == m)
					pd[i][k] |= pd[j][k - 1];
			}
		}
	}

	bool f = 0;
	for(int i = _; i <= b; i++)
		f |= pd[n][i];

	return f;
}

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

	cin >> n >> _ >> b;

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

	if(_ != 1)
	{
		ll tmp = inf;

		for(int i = 50; i >= 0; i--)
			if(f2(tmp ^ (1LL << i)))
				tmp ^= (1LL << i);

		cout << tmp << endl;
		return 0;
	}

	ll tmp = inf;

	for(int i = 50; i >= 0; i--)
		if(f(tmp ^ (1LL << i)) <= b)
			tmp ^= (1LL << i);

	cout << tmp << endl;
}

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