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>
using namespace std;
typedef long long ll;
inline bool check(ll a, ll b){
return ((a&b) == a);
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n, a, b;
cin >> n >> a >> b;
vector<int> v(n+1);
for(int i=1; i<=n; i++) cin >> v[i];
if(a == 1){
vector<int> dp(n+1); // least k | it is possible to divide in k subarrays
ll mask = ~(1LL<<63);
for(int i=62; i>=0; i--){
dp[0] = 0;
for(int x=1; x<=n; x++) dp[x] = n+1;
for(int x=1; x<=n; x++){
ll sum = 0;
for(int y=x; y>=1; y--){
sum += v[y];
if(check(sum, mask^(1LL<<i))) dp[x] = min(dp[x], 1 + dp[y-1]);
}
}
if(dp[n] <= b) mask ^= (1LL<<i);
}
cout << mask << "\n";
}
else{
ll mask = ~(1LL<<63);
for(int i=62; i>=0; i--){
vector<bitset<101>> dp(n+1); // it is possible to divide in k subarrays
dp[0][0] = 1;
for(int y=1; y<=n; y++){
ll sum = 0;
for(int z=y; z>=1; z--){
sum += v[z];
if(check(sum, mask^(1LL<<i))) dp[y] |= dp[z-1]<<1;
}
}
for(int x=a; x<=b; x++){
if(dp[n][x]){
mask ^= (1LL<<i);
break;
}
}
}
cout << mask << "\n";
}
return 0;
}
# | 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... |