Submission #475721

#	Time	Username	Problem	Language	Result	Execution time	Memory
475721		thiago_bastos	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1077 ms	22860 KiB

sculpture

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int N = 2e3, inf = 1e9;

i64 c[N][N];
bitset<101> dp[101];
vector<int> DP;
int n, l, r;

bool sub1(i64 mask, i64 X) {
	
	fill(DP.begin(), DP.end(), inf);
				
	i64 S = mask | X;
				
	for(int i = 0; i < n; ++i) {
		if((c[0][i] & ~S) <= X) DP[i] = 1;
		for(int j = i + 1; j < n; ++j) if((c[i + 1][j] & ~S) <= X) DP[j] = min(DP[j], DP[i] + 1);
	}
	
	if(DP.back() <= r) return true;

	return false;
}

bool sub2(i64 mask, i64 X) {

	for(int i = 0; i < n; ++i) dp[i].reset();
				
	i64 S = mask | X;
				
	for(int i = 0; i < n; ++i) {
		if((c[0][i] & ~S) <= X) dp[i][1] = 1;
		for(int j = i - 1; j >= 0; --j) {
			if((c[j + 1][i] & ~S) <= X) dp[i] = dp[i] | (dp[j] << 1);
		}
	}
				
	for(int i = l; i <= r; ++i) if(dp[n - 1][i]) return true;
			
	return false;
}

void solve() {
	
	cin >> n >> l >> r;
	
	vector<int> a(n);
	DP.resize(n);
	
	for(int i = 0; i < n; ++i) cin >> a[i];
	
	for(int i = 0; i < n; ++i) {
		i64 x = 0;
		for(int j = i; j < n; ++j) c[i][j] = x += a[j];
	}
	
	if(l == 1) {
		i64 mask = 0;
		
		for(int m = 41; m > 0; ) {
			if(sub1(mask, 0)) break;
			for(int k = 0; k < m; ++k) {
				if(sub1(mask, 1LL << k)) {
					mask |= 1LL << k;
					m = k;
					break;
				}
			}
		}
		
		cout << mask << '\n';
	} else {
		i64 mask = 0;
		
		for(int m = 41; m > 0; ) {
			if(sub2(mask, 0)) break;
			for(int k = 0; k < m; ++k) {
				if(sub2(mask, 1LL << k)) {
					mask |= 1LL << k;
					m = k;
					break;
				}
			}
		}
		
		cout << mask << '\n';
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

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