Submission #953871

#	Time	Username	Problem	Language	Result	Execution time	Memory
953871		4QT0R	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	72 ms	756 KiB

sculpture

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

ll dp[2003];
ll sm[2003];
ll oo=1e18;

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

	ll n,a,b;
	cin >> n >> a >> b;
	for (ll i = 1; i<=n; i++){
		cin >> sm[i];
		sm[i]+=sm[i-1];
	}
	ll ans=((ll)1<<41)-1;
	for (ll u = 40; u>=0; u--){
		ll cur=ans-((ll)1<<u);
		for (ll i = 1; i<=n; i++){
			dp[i]=oo;
			for (ll j = 0; j<i; j++){
				if ((cur|(sm[i]-sm[j]))==cur)dp[i]=min(dp[i],1+dp[j]);
			}
		}
		if (a<=dp[n] && dp[n]<=b){
			ans=cur;
		}
	}
	cout << ans << '\n';
}

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