Submission #736577

#	Time	Username	Problem	Language	Result	Execution time	Memory
736577		minhcool	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	75 ms	396 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, a, b, arr[N];
int pref[N];

bool ok[105][105];
int mini[N];

bool ck(int x){
	//cout << x << "\n";
	if(n <= 100){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++) ok[i][j] = 0;
		}
		ok[0][0] = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				for(int lst = 1; lst <= i; lst++){
					if(((pref[i] - pref[lst - 1]) | x) != x) continue;
					ok[i][j] |= ok[lst - 1][j - 1];
				}
			//	cout << i << " " << j << " " << ok[i][j] << "\n";
			}
		}
		for(int i = a; i <= b; i++) if(ok[n][i]) return 1;
		return 0;
	}
	else{
		for(int i = 0; i <= n; i++) mini[i] = oo;
		mini[0] = 0;
		for(int i = 1; i <= n; i++){
			for(int lst = 1; lst <= i; lst++){
				if(((pref[i] - pref[lst - 1]) | x) != x) continue;
				mini[i] = min(mini[i], mini[lst - 1] + 1);
			}
		}
		return (mini[n] <= b);
	}
}

void process(){
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
		pref[i] = pref[i - 1] + arr[i];
	}
	int cur = (1LL << 41) - 1;
	for(int i = 40; i >= 0; i--) if(ck(cur - (1LL << i))) cur -= (1LL << i);
	cout << cur << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

/*
6 1 3
8 1 2 1 5 4
*/

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