Submission #389621

#	Time	Username	Problem	Language	Result	Execution time	Memory
389621		milleniumEeee	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	190 ms	4300 KiB

sculpture

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;

const int MAXN = 2005;
const int INF = 1e18;

int y[MAXN];
int pref[MAXN];
int n, a, b;

int get_sum(int l, int r) {
	return pref[r] - pref[l - 1];
}
bool in(int small, int big) {
	return ((big & small) == small);
}

namespace subtask4 {
	bool dp[MAXN][MAXN];	
	bool check(int x) {
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int gr = 1; gr <= b; gr++) {
			for (int i = gr; i <= n; i++) {
				for (int last = 0; last < i; last++) {
					if (dp[gr - 1][last] && in(get_sum(last + 1, i), x)) {
						dp[gr][i] = 1;
					}
				}
			}
		}
		for (int gr = a; gr <= b; gr++) {
			if (dp[gr][n]) {
				return true;
			}
		}
		return false;
	}
	void solve() {
		int cur = (1ll << 63) - 1;
		for (int i = 62; i >= 0; i--) {
			if (check(cur ^ (1ll << i))) {
				cur ^= (1ll << i);
			}
		}
		cout << cur << endl;	
		exit(0);
	}
};

signed main() {
	fastInp;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		cin >> y[i];
		pref[i] = pref[i - 1] + y[i];
	}
	if (a > 1) {
		subtask4::solve();
	} else {
		auto check = [&](int x) {
			vector <int> dp(MAXN, INF);
			dp[0] = 0;
			for (int i = 0; i < n; i++) {
				if (dp[i] == INF) {
					continue;
				}
				for (int j = i + 1; j <= n; j++) {
					if (in(get_sum(i + 1, j), x)) {
						dp[j] = min(dp[j], dp[i] + 1);
					}
				}
			}
			return dp[n] <= b;
		};
		int cur = (1ll << 63) - 1;
		for (int i = 62; i >= 0; i--) {
			if (check(cur ^ (1ll << i))) {
				cur ^= (1ll << i);
			}
		}
		cout << cur << endl;
	}
}
/*
6 1 3
8 1 2 1 5 4
*/

Compilation message (stderr)

sculpture.cpp: In function 'void subtask4::solve()':
sculpture.cpp:48:25: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
   48 |   int cur = (1ll << 63) - 1;
      |             ~~~~~~~~~~~~^~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:84:25: warning: integer overflow in expression of type 'long long int' results in '9223372036854775807' [-Woverflow]
   84 |   int cur = (1ll << 63) - 1;
      |             ~~~~~~~~~~~~^~~

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