Submission #373746

#	Time	Username	Problem	Language	Result	Execution time	Memory
373746		srvlt	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	804 ms	16248 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mem(x, y) memset(& x, y, sizeof(x))
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
using namespace std;

const int n0=2003,n1=103;
int n,a,b,dp[n1][n1];
ll v[n0],ans;

int d[n0],g[n0][n0];
queue<int> q;
int bfs(int s) {
	mem(d,0x3f);
	d[s]=0;
	q.push(s);
	while(!q.empty()) {
		int v=q.front();q.pop();
		for(int i=0; i<=n; i++) {
			if(g[v][i] && d[i]>n0) {
				d[i]=d[v]+1;
				q.push(i);
			}
		}
	}
	return d[n];
}
bool ok(ll x) {
	if(n<n1) {
		mem(dp,0);
		dp[0][0]=1;
		for(int i=1; i<=b; i++) {
			for(int j=i; j<=n; j++) {
				for(int k=0; k<j; k++) {
					ll s=v[j]-v[k];
					if((s&x)!=s || !dp[i-1][k]) continue;
					dp[i][j]=1;
					break;
				}
			}
			if(i>=a && dp[i][n]) return 1;
		}
		return 0;
	}	else {
		assert(a==1);
		mem(g,0);
		for(int i=0; i<=n; i++) {
			for(int j=i+1; j<=n; j++) {
				ll s=v[j]-v[i];
				if((s&x)==s) {
					g[i][j]=1;
				}
			}
		}
		return bfs(0)<=b;
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> a >> b;
	for(int i=1; i<=n; i++) cin >> v[i],v[i]+=v[i-1];
	for(int i=45; i>=0; i--) {
		ll t=(1ll<<i)-1;
		if(!ok(ans|t)) ans|=1ll<<i;
	}
	cout << ans;
}

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