Submission #523704

#	Time	Username	Problem	Language	Result	Execution time	Memory
523704		Gurban	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	123 ms	364 KiB

sculpture

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

using ll = long long;

const int maxn=2e3+5;
int n,A,B;
int a[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> A >> B;
	for(int i = 1;i <= n;i++) cin >> a[i];

	ll ans = 0;

	if(n <= 100){
		for(ll i = 41;i >= 0;i--){
			ll now = ans + (1ll << i) - 1;
			vector<vector<int>>dp(n + 1,vector<int>(n + 1,0));
			dp[0][0] = 1;
			for(int j = 1;j <= n;j++){
				ll sum = 0;
				for(int k = j;k >= 1;k--){
					sum += a[k];
					if((sum & now) == sum) for(int cnt = 1;cnt <= j;cnt++) dp[j][cnt] |= dp[k - 1][cnt - 1];
				}
			}
			bool tr = 0;
			for(int k = A;k <= B;k++) tr |= dp[n][k];
			if(!tr) ans += (1ll << i);
		}
		cout<<ans;
		return 0;
	}

	for(ll i = 41;i >= 0;i--){
		ll now = ans + (1ll << i) - 1;
		vector<int>dp(n + 1,1e9);
		dp[0] = 0;
		for(int j = 1;j <= n;j++){
			ll sum = 0;
			for(int k = j;k >= 1;k--){
				sum += a[k];
				if((sum & now) == sum) dp[j] = min(dp[j],dp[k - 1] + 1);
			}
		}
		if(dp[n] > B) ans += (1ll << i); 
	}
	cout<<ans;
}

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