This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |