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;
#define name "main"
const int maxlog=(int)40;
const int N=(int)2000;
ll arr[N+2]={};
ll ans=((ll)1<<maxlog)-1;
ll dp[N+2][N+2]={};
int n,a,b;
bool possible(ll limit){
memset(dp,0x3f,sizeof dp);
int INF=dp[0][0];
dp[0][0]=0;
for (int i=1;i<=n;++i){
ll tot=0;
for (int j=i;j<=n;++j){
tot+=arr[j];
if ((tot&limit)!=tot) continue;
if (a==1) dp[j][1]=min(min(dp[i-1][0],dp[i-1][1])+1,dp[j][1]);
else{
for (int block=1;block<=min(i,b);++block){
dp[j][block]=min(dp[i-1][block-1]+1,dp[j][block]);
}
}
}
}
if (a==1){
if (dp[n][1]<=b) return true;
return false;
}
for (int i=a;i<=b;++i)
if (dp[n][i]!=i) return false;
return true;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>a>>b;
for (int i=1;i<=n;++i) cin>>arr[i];
for (int i=maxlog-1;i>=0;--i){
if (possible(ans^((ll)1<<i))) {
ans^=((ll)1<<i);
}
}
cout<<ans;
exit(0);
}
Compilation message (stderr)
sculpture.cpp: In function 'bool possible(ll)':
sculpture.cpp:16:6: warning: unused variable 'INF' [-Wunused-variable]
16 | int INF=dp[0][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... |