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 ll long long
using namespace std;
int N,A,B;
ll sums[2010],arr[2010];
bool check1(ll val){
vector<vector<bool>> dp(N+1,vector<bool>(N+1,false));
dp[0][0] = true;
for(int i = 1;i<=N;++i){
for(int j = 1;j <= B && j <= i;++j){
for(int k = i-1;k>=0;--k){
if(dp[k][j-1] && ((sums[i]-sums[k])|val) <= val){
dp[i][j] = true;
break;
}
}
}
}
for(int i = A;i<=B;++i){
if(dp[N][i]) return true;
}
return false;
}
bool check2(ll val){
vector<int> dp2(N+1,0);
for(int i = 1;i<=N;++i){
dp2[i] = B+1;
for(int j = i-1;j>=0;--j){
if(((sums[i]-sums[j])|val) <= val && dp2[j]+1 < dp2[i]){
dp2[i] = dp2[j]+1;
}
}
}
return dp2[N] <= B;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> A >> B;
for(int i = 1;i<=N;++i){
cin >> arr[i];
sums[i] = sums[i-1]+arr[i];
}
if(A == 1){
ll ans = (1ll<<41)-1;
for(int i = 40;i>=0;--i){
if(check2(ans^(1ll<<i))){
ans ^= (1ll<<i);
}
}
cout << ans << "\n";
}
else{
ll ans = (1ll<<41)-1;
for(int i = 40;i>=0;--i){
if(check1(ans^(1ll<<i))){
ans ^= (1ll<<i);
}
}
cout << ans << "\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... |