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;
int n,a,b;
int arr[2001];
int dp[2002][2011];
int place;
long long res=0;
int get(int cur,int r){
if(cur==n+1){
if(a<=r && r<=b)return 1;
return 0;
}
if(dp[cur][r]!=-1)return dp[cur][r];
long long sum=0;
int ok=0;
for(int i=cur;i<=n;i++){
sum+=arr[i];
if((res >> (place+1))==((res|sum) >> (place+1))){
if((sum & (1LL << place))==0)
ok=max(ok,get(i+1,r+1));
}
}
return dp[cur][r]=ok;
}
int get2(int cur){
if(cur==n+1)return 0;
if(dp[cur][0]!=-1)return dp[cur][0];
long long sum=0;
int r=100000;
for(int i=cur;i<=n;i++){
sum+=arr[i];
if((res >> (place+1))==((res|sum) >> (place+1))){
if((sum & (1LL << place))==0)
r=min(r,1+get2(i+1));
}
}
return dp[cur][0]=r;
}
int main(void){
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >>n >> a >> b;
for(int i=1;i<=n;i++)
cin >> arr[i];
if(a>1){
for(place=40;place>=0;place--){
memset(dp,-1,sizeof(dp));
if(!get(1,0)){
res+=(1LL << place);
}
}
cout << res;
}
else{
for(place=40;place>=0;place--){
memset(dp,-1,sizeof(dp));
if(get2(1)>b){
res+=(1LL << place);
}
}
cout << res;
}
}
# | 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... |