Submission #583133

#	Time	Username	Problem	Language	Result	Execution time	Memory
583133		YesPy	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	1 ms	340 KiB

sculpture

#include <bits/stdc++.h>

#define mins(i, j) (i = min(i, j))
#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;

using namespace std;

typedef long long ll;

int N, A, B, dp[2002][2002];
ll ans = 1, pref[2002];

int go1(ll mask) {
	dp[0][0] = 0;
	for(int i=1; i<=N; ++i) dp[i][0] = N;

	for(int i=1; i<=N; ++i) {
		for(int j=0; j<i; ++j) {
			if(((pref[i]-pref[j])|mask) == mask) mins(dp[i][0], (dp[j][0]+1));
		}
	}

	return (dp[N][0] <= B);
}

int go2(ll mask) {
	int res = 0;
	dp[0][0] = 1;

	for(int i=0; i<=N; ++i) {
		for(int j=0; j<=B; ++j) dp[i][j] = 0;
	}

	for(int i=1; i<=N; ++i) {
		for(int j=1; j<=B; ++j) {
			for(int k=0; k<i; ++k) dp[i][j] |= dp[k][j-1] & (((pref[i]-pref[k])|mask) == mask);
		}
	}

	for(int X=A; X<=B; ++X) res |= dp[N][X];
	return res;
}

int main()
{
	fastio
	cin>>N>>A>>B, ans <<= 41, --ans;
	for(int i=1; i<=N; ++i) cin>>pref[i], pref[i] += pref[i-1];

	for(int i=40; i>=0; --i) {
		if(A == 1 && go1(ans^(1LL<<i))) ans ^= (1LL<<i);
		if(A > 1 && go2(ans^(1LL<<i))) ans ^= (1LL<<i);
	}

	cout<<ans<<ln;

	return 0;
}

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