Submission #766927

#	Time	Username	Problem	Language	Result	Execution time	Memory
766927		vito	Bali Sculptures (APIO15_sculpture)	C++98	0 / 100	1094 ms	340 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX1=2001;
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;
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) {
			dp1[i]=min(dp1[i], 1+rek1(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=42; ~i; i--) {
			t^=(1LL<<i);
			for(int j=0; j<MAX1; j++) {
				dp1[j]=INF;
			}
			ok=0;
			dp1[n]=0;
			rek1(0);
			if(dp1[0]>B) {
				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;
			}
		}
		rek2(0, 0);
		if(ok) {
			t^=(1LL<<i);
		}
	}
	cout << t << '\n';
}

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