Submission #552599

#	Time	Username	Problem	Language	Result	Execution time	Memory
552599		QwertyPi	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	73 ms	95012 KiB

sculpture

#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;
const int N = 2001;
int dp[N][N], dp2[N];
int s[N], A[N];
vector<int> vals[N][N];
typedef uint32_t uint;
bool valid[N][N];
int n, a, b;
bool check(int mask){
	for(int i = 0; i < n; i++){
		for(int j = i; j < n; j++){
			int v = s[j + 1] - s[i];
			valid[i][j] = (v | mask) == mask;
		}
	}
	if(n > 100){
		fill(dp2 + 1, dp2 + n + 1, INF);
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= i; j++){
				dp2[i + 1] = min(dp2[i + 1], dp2[j] + valid[j][i]);
			}
		}
		return dp2[n] <= b;
	}else{
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				dp[i][j] = false;
			}
		}
		dp[0][0] = true;
		for(int tr = 0; tr < n; tr++){
			for(int i = 0; i < n; i++){
				for(int j = i; j < n; j++){
					dp[tr + 1][j + 1] |= dp[tr][i] & valid[i][j];
				}
			}
		}
		bool ans = false;
		for(int i = a; i <= b; i++){
			ans |= dp[i][n];
		}
		return ans;
	}
}

int32_t main(){
	cin >> n >> a >> b;
	vals[0][0].push_back(0);
	for(int i = 1; i <= n; i++) cin >> A[i], s[i] = s[i - 1] + A[i];
	uint mask = 0;
	for(int j = 60; j >= 0; j--){
		if(!check(mask + (1LL << j) - 1)){
			mask += 1LL << j;
		}
	}
	cout << mask << endl;
}

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