Submission #110023

#	Time	Username	Problem	Language	Result	Execution time	Memory
110023		aminra	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	438 ms	31992 KiB

sculpture

//I forgot you...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = 2003;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e18;
ll n, A, B, dp[MAXN][MAXN], a[MAXN], part[MAXN];
ll dist[MAXN];
vector<ll> G[MAXN];
void calc()
{
	dp[0][0] = 1;
	for (int i = 0; i <= n - 1; i++)
		for (int j = 0; j <= i; j++)
			if(dp[i][j])
				for (auto u : G[i])
					dp[u][j + 1] = 1;
}
void calc2()
{
	dist[0] = 0;
	for (int i = 0; i <= n - 1; i++)
		for (auto u : G[i])
			dist[u] = min(dist[u], dist[i] + 1);
}
int main()
{
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		part[i] = part[i - 1] + a[i];
	if(A == 1)
	{
		ll ans = 0;
		for (ll i = 50; i >= 0; i--)
		{
			ans += (1LL << i);
			for (int j = 0; j <= n; j++)
				G[j].clear();
			memset(dist, 63, sizeof dist);
			for (ll j = 0; j <= n; j++)
				for (ll k = j + 1; k <= n; k++)
					if(((part[k] - part[j]) & ans) == 0)
						G[j].push_back(k);
			calc2();
			bool mika = (dist[n] <= B);
			if(mika == 0)
				ans -= (1LL << i);
		}
		cout << (1LL << 51) - 1 - ans;
		return 0;
	}
	ll ans = 0;
	for (ll i = 50; i >= 0; i--)
	{
		ans += (1LL << i);
		for (int j = 0; j <= n; j++)
			G[j].clear();
		memset(dp, 0, sizeof dp);
		for (ll j = 0; j <= n; j++)
			for (ll k = j + 1; k <= n; k++)
				if(((part[k] - part[j]) & ans) == 0)
					G[j].push_back(k);
		calc();
		bool mika = 0;
		for (int X = A; X <= B; X++)
			if(dp[n][X])
				mika = 1;
		if(mika == 0)
			ans -= (1LL << i);
	}
	cout << (1LL << 51) - 1 - ans;
}

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