Submission #373927

#	Time	Username	Problem	Language	Result	Execution time	Memory
373927		nafis_shifat	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	111 ms	492 KiB

sculpture

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int n,a,b;
ll x[mxn];
ll cum[mxn];
ll cur = 0;
bool check1(int k) {
	ll p = cur | ((1ll << k) - 1);

	int dp[n + 1];

	dp[0] = 0;

	for(int i = 1; i <= n; i++) {
		dp[i] = inf;
		for(int j = i - 1; j >= 0; j--) {
			ll k = cum[i] - cum[j];
			if((p&k) == k) dp[i] = min(dp[i],dp[j] + 1);
		}
	}


	return dp[n] <= b;
}

bool check2(int k) {
	ll p = cur | ((1ll << k) - 1);
	bool dp[n + 1][b + 1] = {};


	dp[0][0] = true;

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= b; j++) {
			for(int k = i - 1; k >= 0; k--) {
				ll sm = cum[i] - cum[k];

				if((p&sm) == sm) dp[i][j] |= dp[k][j - 1];
			}
			
	    }
	}

	for(int i = a; i <= b; i++) if(dp[n][i]) return true;
	return false;

}
int main() {
	cin >> n >> a >> b;
	cum[0] = 0;
	for(int i = 1; i <= n; i++) {
		cin>>x[i];
		cum[i] = cum[i - 1] + x[i];
	}


	for(int i = 40; i >= 0; i--) {
		int f;
		if(a == 1) f = check1(i);
		else f = check2(i);

		if(!f) cur |= 1ll << i;


	}
	cout<<cur<<endl;

}

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