Submission #237587

#	Time	Username	Problem	Language	Result	Execution time	Memory
237587		wwdd	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	83 ms	512 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MB = 42;
const int MN = 2020;
const int NN = 102;
const int INF = 1e9;
ll pr[MN];
ll da[MN];
ll db[NN][NN];
ll n,a,b;
bool dpa(ll bm) {
	fill(begin(da),end(da),INF);
	da[0] = 0;
	for(int i=0;i<n;i++) {
		if(da[i] >= b) {continue;}
		for(int j=i+1;j<=n;j++) {
			ll wal = pr[j]-pr[i];
			if((wal&bm) == wal) {
				da[j] = min(da[j],da[i]+1);
			}
		}
	}
	return (da[n] <= b);
}
bool dpb(ll bm) {
	memset(db,0,sizeof(db));
	db[0][0] = 1;
	for(int i=0;i<n;i++) {
		for(int j=0;j<b;j++) {
			if(!db[i][j]) {
				continue;
			}
			for(int k=i+1;k<=n;k++) {
				ll wal = pr[k]-pr[i];
				if((wal&bm) == wal) {
					db[k][j+1] = 1;
				}
			}
		}
	}
	for(int i=a;i<=b;i++) {
		if(db[n][i]) {return true;}
	}
	return false;
}
int main() {
	cin >> n >> a >> b;
	pr[0] = 0;
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		pr[i+1] = pr[i]+t;
	}
	ll res = (1LL<<MB)-1;
	for(int ba=MB-1;ba>=0;ba--) {
		bool bop;
		if(a > 1) {
			bop = dpb(res^(1LL<<ba));
		} else {
			bop = dpa(res^(1LL<<ba));
		}
		//cout << "bop it " << res << '\n';
		if(bop) {res ^= (1LL<<ba);}
	}
	cout << res << '\n';
}

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