Submission #531102

#	Time	Username	Problem	Language	Result	Execution time	Memory
531102		buidangnguyen05	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	100 ms	348 KiB

sculpture

/* input

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2010, M = 110;
int n, L, R, f[N]; ll pref[N];
bool dp[M][M];

void sub1234() {
	ll cur = 0;
	for (int bit = 36; ~bit; --bit) {
		memset(dp, 0, sizeof(dp)); dp[0][0] = 1;
		cur |= (1LL << bit);
		for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
			for (int k = i; k; --k) {
				ll sum = pref[i] - pref[k - 1];
				if (!(sum & cur)) dp[i][j] |= dp[k - 1][j - 1];
			}
		}
		bool ok = 0;
		for (int i = L; i <= R; ++i) if (dp[n][i]) ok = 1;
		if (!ok) cur ^= (1LL << bit);
	}
	for (int bit = 36; ~bit; --bit) cur ^= (1LL << bit);
	cout << cur << "\n";
}

void sub5() {
	ll cur = 0;
	for (int bit = 40; ~bit; --bit) {
		fill (f + 1, f + n + 1, n + 1);
		cur |= (1LL << bit);
		for (int i = 1; i <= n; ++i) for (int j = i; j; --j) {
			ll sum = pref[i] - pref[j - 1];
			if (!(sum & cur)) f[i] = min(f[i], f[j - 1] + 1);
		}
		if (f[n] > R) cur ^= (1LL << bit);
	}
	for (int bit = 40; ~bit; --bit) cur ^= (1LL << bit);
	cout << cur << "\n";
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("task.inp", "r")) {
		freopen("task.inp", "r", stdin);
		freopen("task.out", "w", stdout);
	}
	
	cin >> n >> L >> R;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		pref[i] = pref[i - 1] + x;
	}

	if (n <= 100) sub1234();
	else sub5();
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:50:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   freopen("task.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:51:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   freopen("task.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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