Submission #882912

#	Time	Username	Problem	Language	Result	Execution time	Memory
882912		Onur_Ilgaz	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	113 ms	604 KiB

sculpture

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
vector <int> arr(2001), pref(2001);

bool solve(int val, int n, int a, int b) {
	vector<int> dp(n + 1, inf);
	dp[0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int from = 0; from < i; from++) {
			if(((pref[i] - pref[from]) & val) == 0) {
				dp[i] = min(dp[i], dp[from] + 1); // dp[i] = i'ye kadar min kaç bölmelendirmeyle value'ya ulaşılabilinir
			}
		}
	}
	return (dp[n] <= b);
}

bool solve2(int val, int n, int a, int b) {
	vector<vector<bool> > dp(n + 1, vector<bool>(n + 1));
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int cnt = 1; cnt <= b; cnt++){
			for(int from = 0; from < i; from++) {
				if(dp[from][cnt-1] && (((pref[i] - pref[from]) & val) == 0)) {
					dp[i][cnt] = 1;
				}
			}
		}
	}
	for(int i = a; i <= b; i++) {
		if(dp[n][i] == 1) return 1;
	}
	return 0;
}

int32_t main(){
	fast
	int n, a, b;
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		pref[i] = pref[i-1] + arr[i];
	}
	int val = 0;
	for(int bit = (1ll << 60ll); bit > 0; bit /= 2) {
		bool ans;
		if(n > 100) ans = solve(val + bit, n, a, b);
		else ans = solve2(val + bit, n, a, b);
		val += ans * bit;
	}
	cout << (((1ll << 61ll) - 1) ^ val) << "\n";
}

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