제출 #1332545

#제출 시각아이디문제언어결과실행 시간메모리
1332545vache_kocharyanBali Sculptures (APIO15_sculpture)C++20
100 / 100
98 ms632 KiB
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

const bool debug = false;

#define ff first
#define ss second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define YN(x) if(x)yes; else no;
#define all(X) (X).begin(), (X).end()
#define rall(X) (X).rbegin(), (X).rend()

const int N = 2e3 + 5;
const long long mod = 1e9 + 7;

long long mult(long long a, long long b)
{
	return (a * b) % mod;
}

long long binpow(long long a, long long b) {
	long long res = 1;
	a %= mod;
	while (b > 0) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

long long m_inverse(long long n) {
	return binpow(n, mod - 2);
}

long long divide(long long a, long long b) {
	return (a % mod * m_inverse(b)) % mod;
}

long long sub(long long a, long long b)
{
	if (a - b >= 0)return a - b;
	else return a - b + mod;
}

long long add(long long a, long long b)
{
	if (a + b >= mod)return a + b - mod;
	else return a + b;
}

const int LOG = 60;
long long x[N];
int dp[N];
bool dp1[N][N];

void solve()
{
	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
		cin >> x[i];

	if (a == 1) {
		ll ans = (1ll << (LOG + 1)) - 1ll;
		ll cur = 0;
		for (int bt = LOG; bt >= 0; bt--)
		{
			for (int i = 1; i <= n; i++)
			{
				dp[i] = 1e9;
			}
			dp[0] = 0;
			ll h = (1ll << (LOG + 1)) - (1ll << (bt));
			for (int i = 1; i <= n; i++)
			{
				ll s = 0;
				for (int j = i; j >= 1; j--)
				{
					s += x[j];
					if (((h & s) | cur) == cur)
						dp[i] = min(dp[i], dp[j - 1] + 1);
				}
			}

			if (debug) {
				for (int i = 1; i <= n; i++)
				{
					cout << dp[i] << " ";
				}
				cout << endl;
				cout << "bt " << bt << " " << ans << " " << cur << endl;
			}
			if (dp[n] <= b)
			{
				ans -= (1ll << bt);
			}
			else
			{
				cur += (1ll << bt);
			}
		}
		cout << ans << endl;
	}
	else
	{
		ll ans = (1ll << (LOG + 1)) - 1ll;
		ll cur = 0;
		for (int bt = LOG; bt >= 0; bt--)
		{
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					dp1[i][j] = false;
				}
			}
			dp1[0][0] = true;
			ll h = (1ll << (LOG + 1)) - (1ll << (bt));
			for (int j = 1; j <= n; j++)
			{
				for (int i = 1; i <= n; i++)
				{
					ll s = 0;
					for (int J = i; J >= 1; J--)
					{
						s += x[J];
						if (((h & s) | cur) == cur)
							dp1[i][j] |= dp1[J - 1][j - 1];
					}
				}
			}

			if (debug) {
				for (int i = 1; i <= n; i++)
				{
					cout << dp[i] << " ";
				}
				cout << endl;
				cout << "bt " << bt << " " << ans << " " << cur << endl;
			}
			bool B = false;
			for (int j = a; j <= b; j++)
			{
				if (B)break;
				if (dp1[n][j])
				{
					B = true;
				}
			}

			if (B)
			{
				ans -= (1ll << bt);
			}
			else
			{
				cur += (1ll << bt);
			}
		}
		cout << ans << endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	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...