제출 #1271415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271415		cmiuc	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	115 ms	584 KiB

sculpture

#include <iostream>

using namespace std;
#define int long long
const int N = 205;
int dp[N * 10], Dp[N][N], a[N * 10], Pre[N * 10], n, A, B, o = 1, Ans, And;

int Dp1(){
	for (int i=0;i<=n;i++)
		dp[i] = 1e9;
	dp[0] = 0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<i;j++){
			int s = Pre[i] - Pre[j];
			if ((Ans | (s & And)) == Ans)
				dp[i] = min(dp[i], dp[j] + 1);
		}
	}
	return dp[n];
}

void solve1(){
	for (int b=60;b>=0;b--){
		And |= (o<<b);
		if (Dp1() > B)
			Ans |= (o<<b);
	}
}

bool Dp2(){
	for (int i=0;i<=n;i++){
		for (int j=0;j<=n;j++)
			Dp[i][j] = 0;
	}
	Dp[0][0] = 1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			for (int k=0;k<i;k++){
				int s = Pre[i] - Pre[k];
				if ((Ans | (s & And)) == Ans)
					Dp[i][j] |= Dp[k][j-1];
			}
		}
	}
	for (int i=A;i<=B;i++)
		if (Dp[n][i])
			return 1;
	return 0;
}


void solve2(){
	for (int b=60;b>=0;b--){
		And |= (o<<b);
		if (Dp2() == 0)
			Ans |= (o<<b);
	}
}


signed main(){
	cin>>n>>A>>B;

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

	if (A == 1)
		solve1();
	else
		solve2();
	cout<<Ans<<'\n';
}

/*

6 1 3
8 1 2 1 5 4

*/

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