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 owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
vector<ll> arr;
vector<ll> psum;
int dp[2002][2002];
int n, a, b;
ll currbest = 0;
bool solve(ll bit) {
ll mx = currbest+(1LL<<bit);
if(a==1) {
owo(i, 0, n+1) {
dp[0][i] = INF;
}
dp[0][0] = 0;
owo(i, 0, n) {
owo(j, 0, i+1) {
//cout<<currbest<<" "<<(psum[i+1]-psum[j])<<" "<<(currbest|(psum[i+1]-psum[j]))<<" "<<mx<<"\n";
if((currbest|(psum[i+1]-psum[j]))<mx) {
dp[0][i+1] = min(dp[0][i+1] , dp[0][j] + 1);
}
}
}
return dp[0][n]>b;
}else {
owo(i, 0, 2002) {
owo(j, 0, 2002) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
owo(i, 0, n) {
owo(j, 0, i+1) {
if((currbest|(psum[i+1]-psum[j]))<mx) {
owo(k, 0, b) {
if(dp[j][k]) {
dp[i+1][k+1] = 1;
}
}
}
}
}
for(int i=a; i<=b; ++i) {
if(dp[n][i]) {
return false;
}
}
return true;
}
}
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n>>a>>b;
arr.resize(n);
psum.resize(n+1);
psum[0] = 0;
owo(i, 0, n) {
cin>>arr[i];
psum[i+1] = psum[i] + arr[i];
}
for(ll i = 35; i>=0; --i) {
if(solve(i)) {
currbest+=(1LL<<i);
}
}
cout<<currbest<<"\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... |