제출 #766823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766823		vito	Bali Sculptures (APIO15_sculpture)	C++98	71 / 100	16 ms	464 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX1=51;
const int MAX2=101;
const int INF=1e9+5;
int dp1[MAX1];
int dp2[MAX2][MAX2];
vector<int> a(MAX2);
int n, A, B, nas;
ll t=(1LL<<43)-1;
int ok;
void rek1(int i, int sof) {
	if(sof==B+1) {
		return;
	}
	if(i==n) {
		ok=1;
		return;
	} 
	ll sum=0;
	for(int j=i; j<n; j++) {
		sum+=a[j];
		if((sum|t)==t) {
			dp1[j]=min(dp1[j], 1+(i?dp1[i-1]:0));
			rek1(j+1, sof+1);
		}
	}
}
void rek2(int i, int sof) {
	if(sof==B+1) {
		return;
	}
	if(i==n && sof>=A) {
		ok=1;
		return;
	}
	ll sum=0;
	for(int j=i; j<n; j++) {
		sum+=a[j];
		if((sum|t)==t) {
			if(dp2[j+1][sof+1]) {
				continue;
			}
			dp2[j+1][sof+1]=1;
			rek2(j+1, sof+1);
		}
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	// if(A==1) {
	// 	for(int i=42; ~i; i--) {
	// 		t^=(1LL<<i);
	// 		for(int j=0; j<MAX1; j++) {
	// 			dp1[j]=INF;
	// 		}
	// 		ok=0;
	// 		rek1(0, 0);
	// 		if(ok==0) {
	// 			t^=(1LL<<i);
	// 		}
	// 	}
	// 	cout << t << '\n';
	// 	return 0;
	// }
	for(int i=42; ~i; i--) {
		t^=(1LL<<i);
		for(int j=0; j<MAX2; j++) {
			for(int k=0; k<MAX2; k++) {
				dp2[j][k]=0;
			}
		}
		ok=0;
		rek2(0, 0);
		if(ok==0) {
			t^=(1LL<<i);
		}
	}
	cout << t << '\n';
}

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