Submission #860692

#	Time	Username	Problem	Language	Result	Execution time	Memory
860692		Iliya_	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	64 ms	604 KiB

sculpture

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef long long ll; 

const ll N = 2e3+7, NN = 1e2+7; 
ll a[N], dp[N], sum[N]; 
bool pd[NN][NN];

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

	ll n,l,r; cin >> n >> l >> r; 
	for(ll i=1; i<=n; i++){
		cin >> a[i]; 
		sum[i] = sum[i-1] + a[i]; 
	}
	if (l != 1){
		ll ans = 0; 
		for(ll ind = 45; ind >= 0; ind--){
			pd[0][0] = 1; 
			for(ll i=1; i<=n; i++) for(ll j=1; j<=n; j++) pd[i][j] = 0; 
			for(ll i=1; i<=n; i++){
				for(ll j=1; j<=i; j++){
					for(ll k=i; k>=1; k--){
						ll maj = sum[i] - sum[k-1]; 
						maj -= (maj & ans);
						if (maj < (1ll<<ind)) pd[i][j] |= pd[k-1][j-1];
					}
				}
			}
			bool add = 1;
			for(ll j=l; j<=r; j++) if (pd[n][j]) add = 0; 
			if (add) ans += (1ll<<ind);
		}
		cout << ans << endl;
	}
	else{
		ll ans = 0;
		for(ll ind = 45; ind >= 0; ind--){
			dp[0] = 0; 
			for(ll i=1; i<=n; i++){
				dp[i] = 1e9; 
				for(ll j=i; j>=1; j--){
					ll maj = sum[i] - sum[j-1]; 
					maj -= (maj & ans); 
					if (maj < (1ll<<ind)) dp[i] = min(dp[i],dp[j-1]+1);  
				}
			}
			if (dp[n] > r) ans += (1ll<<ind);
		}
		cout << ans << endl;
	}

	return 0;
}

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