제출 #953872

#제출 시각아이디문제언어결과실행 시간메모리
9538724QT0RBali Sculptures (APIO15_sculpture)C++17
100 / 100
48 ms600 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define ll long long
 
bitset<2001> dp[2003];
ll sm[2003];
bitset<2001> mv[2003];

ll dp2[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;
	if (a!=1){
		dp[0][0]=1;
		for (ll u = 40; u>=0; u--){
			ll cur=ans-((ll)1<<u);
			for (ll i = 1; i<=n; i++){
				for (ll j = 0; j<i; j++){
					if ((cur|(sm[i]-sm[j]))==cur)mv[i][j]=1;
					else mv[i][j]=0;
				}
				for (ll j = i; j<=n; j++)mv[i][j]=0;
			}
			for (ll i = 1; i<=b; i++){
				for (ll j = 1; j<=n; j++){
					if ((dp[i-1]&mv[j]).any())dp[i][j]=1;
					else dp[i][j]=0;
				}
			}
			for (ll i = a; i<=b; i++){
				if (dp[i][n]){
					ans=cur;
					break;
				}
			}
		}
	}
	else{
		for (ll u = 40; u>=0; u--){
			ll cur=ans-((ll)1<<u);
			for (ll i = 1; i<=n; i++){
				dp2[i]=oo;
				for (ll j = 0; j<i; j++){
					if ((cur|(sm[i]-sm[j]))==cur)dp2[i]=min(dp2[i],1+dp2[j]);
				}
			}
			if (a<=dp2[n] && dp2[n]<=b){
				ans=cur;
			}
		}
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...