Submission #322206

#	Time	Username	Problem	Language	Result	Execution time	Memory
322206		Saynaa	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	87 ms	4480 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 2000 + 5;
const ll ziad = 1e15 + 10;
int n, a[MAXN], A, B;
ll mx = 0;
bool ok[MAXN][MAXN];
ll dp[MAXN];


int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> A >> B;
	for(int i = 0; i < n; i ++)
		cin >> a[i];
	
	if( n <= 300){
	for(int b = 40; b >= 0; b --){
		memset(ok, false, sizeof ok);
		ok[0][0] = true;
		//if( (a[0] & mx) == 0) ok[1][1] = true;
		mx ^= (1LL << b);
		for(int t = 0; t <= n; t ++){
			for(int i = 0; i < n; i ++){
				if( !ok[i][t] ) continue;
				ll sum = 0;
				for(int h = i; h < n; h ++){
					sum += (ll)a[h];
					if( (sum & mx) == 0) ok[h + 1][t + 1] = true;
				}
			}
		}
		bool bit = false;
		for(int i = A; i <= B; i ++)
			bit |= ok[n][i];
		if( !bit )
				mx ^= (1LL << b);
	}
//	cout << mx << endl;
	mx = (1LL << 41) - 1 - mx;
	cout << mx << endl;
	return 0;
	}
	for(int b = 40; b >= 0; b --){
		fill(dp, dp + n + 1, ziad);
		dp[0] = 0;
	//	bool bit = false;
		//if( (a[0] & mx) == 0) ok[1][1] = true;
		mx ^= (1LL << b);
	//	for(int t = 0; t <= n; t ++){
		for(int i = 0; i < n; i ++){
			if( dp[i] >= B ) continue;
			ll sum = 0;
			for(int h = i; h < n; h ++){
				sum += (ll)a[h];
				if( (sum & mx) == 0){
					dp[h + 1] = min(dp[h + 1], dp[i] + 1);
					//
				}
			}
			
		}
	//	}
		if( dp[n] > B )
				mx ^= (1LL << b);
	}
	
	mx = (1LL << 41) - 1 - mx;
	cout << mx << endl;
	return 0;
}

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