Submission #1212021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212021		A_M_Namdar	Bali Sculptures (APIO15_sculpture)	C++20	0 / 100	0 ms	328 KiB

sculpture

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

const long long N = 100 + 10, M = 1e3 + 10;
long long n, l, r, a[M], dp[N][N], dp2[M];

bool check(long long x) {
	for (long long i = 0; i < n; i++) {
		dp2[i + 1] = 1e9 + 10;
		long long s = 0;
		for (long long j = i; j >= 0; j--) {
			s += a[j];
			if ((s & x) == s) 
				dp2[i] = min(dp2[i], dp2[j] + 1);
		}
	}
	return dp2[n] <= r;
}

void input() {
	cin >> n >> l >> r;
	for (long long i = 0; i < n; i++) 
		cin >> a[i];
}

void solve() {
	if (n <= 100) {
		memset(dp, 63, sizeof dp);
		dp[0][0] = 0;
		for (long long i = 0; i < n; i++) {
			for (long long j = 0; j <= i; j++) {
				long long s = 0;
				for (long long k = i; k < n; k++) {
					s += a[k];
					dp[k + 1][j + 1] = min(dp[k + 1][j + 1], (dp[i][j] | s));
				}
			}
		}
		long long ans = 1e9 + 10;
		for (long long i = l; i <= r; i++) 
			ans = min(ans, dp[n][i]);
		cout << ans;
	}
	else {
		long long l = -1, r = 1e9 + 10;
		while (r - l > 1) {
			long long mid = (l + r) / 2;
			if (check(mid)) r = mid;
			else            l = mid;
		}
		cout << r << '\n';
	}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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