제출 #1179071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179071		alexander707070	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	148 ms	476 KiB

sculpture

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

int n,L,R;
int a[MAXN];
long long pref[MAXN];
long long ans;

int dp[MAXN];
bool dp2[107][107];

bool ok(long long x,int bit){
	if((x & (~ans))>=(1LL<<bit))return false;
	return true;
}

void calcdp(int bit){
	for(int i=1;i<=n;i++){
		dp[i]=2*n;

		for(int f=i;f>=1;f--){
			if(ok(pref[i]-pref[f-1],bit))dp[i]=min(dp[i],dp[f-1]+1);
		}
	}
}

void calcdp2(int bit){
	dp2[0][0]=true;
	for(int i=1;i<=R;i++)dp2[0][i]=false;

	for(int i=1;i<=n;i++){
		for(int k=1;k<=R;k++){
			dp2[i][k]=false;

			for(int f=i;f>=1;f--){
				if(ok(pref[i]-pref[f-1],bit) and dp2[f-1][k-1])dp2[i][k]=true;
			}
		}
	}
}

void solve1(){
	for(int i=60;i>=0;i--){
		calcdp(i);
		if(dp[n]>R)ans|=(1LL<<i);
	}

	cout<<ans<<"\n";
}

void solve2(){
	for(int i=60;i>=0;i--){
		calcdp2(i);

		for(int f=L;f<=R;f++){
			if(dp2[n][f])break;
			else if(f==R)ans|=(1LL<<i);
		}
	}

	cout<<ans<<"\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n>>L>>R;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pref[i]=pref[i-1]+a[i];
	}

	if(L==1){
		solve1();
	}else{
		solve2();
	}

	return 0;
}

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