Submission #105860

#	Time	Username	Problem	Language	Result	Execution time	Memory
105860		IOrtroiii	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	137 ms	512 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

int n, l, r;
long long a[2005];

namespace sub4 {
	bool f[105][105];
	bool can(long long val) {
		memset(f, 0, sizeof f);
		f[0][0] = true;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= i; ++j) {
				for (int k = 0; k < i; ++k) {
					if (f[k][j - 1] && ((a[i] - a[k]) | val) == val) {
						f[i][j] = true; break;
					}
				}
			}
		}
		for (int i = l; i <= r; ++i) if (f[n][i]) return true;
		return false;
	}
	void solve() {
		long long val = (1LL << 50) - 1;
		for (int i = 49; i >= 0; --i) {
			if (can(val ^ (1LL << i))) {
				val ^= (1LL << i);
			}
		}
		cout << val << '\n';
	}
}

namespace sub5 {
	int f[2005];
	bool can(long long val) {
		memset(f, 69, sizeof f);
		f[0] = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (((a[i] - a[j]) | val) == val) {
					f[i] = min(f[i], f[j] + 1);
				}
			}
		}
		return f[n] <= r;
	}
	void solve() {
		long long val = (1LL << 50) - 1;
		for (int i = 49; i >= 0; --i) {
			if (can(val ^ (1LL << i))) {
				val ^= (1LL << i);
			}
		}
		cout << val << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> l >> r;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	if (n <= 100) {
		sub4::solve();
	} else {
		sub5::solve();
	}
}

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