Submission #766983

#	Time	Username	Problem	Language	Result	Execution time	Memory
766983		vito	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	82 ms	496 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX1=2001;
const int MAX2=105;
const int INF=1e9+5;
int dp1[MAX1], izr[MAX1];
int dp2[MAX2][MAX2];
vector<int> a(MAX2);
int n, A, B, nas;
ll t=(1LL<<42)-1;
int ok;
int rek1(int i) {
	if(i==n) {
		return 0;
	}
	ll sum=0;
	for(int j=i; j<n; j++) {
		sum+=a[j];
		if((sum|t)==t) {
			if(izr[j+1]==0) {
				izr[j+1]=1;
				dp1[j+1]=rek1(j+1);
			}
			dp1[i]=min(dp1[i], 1+dp1[j+1]);
		}
	}
	return dp1[i];
}
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=41; ~i; i--) {
			t^=(1LL<<i);
			for(int j=0; j<MAX1; j++) {
				dp1[j]=INF;
				izr[j]=0;
			}
			ok=0;
			dp1[n]=0;
			izr[n]=1;
			if(rek1(0)>B) {
				t^=(1LL<<i);
			}
		}
		cout << t << '\n';
		return 0;
	}
	for(int i=41; ~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: 29 / 29