Submission #1028607

#TimeUsernameProblemLanguageResultExecution timeMemory
1028607vjudge1Bali Sculptures (APIO15_sculpture)C++17
71 / 100
13 ms596 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int const N=105; int const inf=1e14; bool dp[N][N]; int dp2[2005]; int arr[N]; int n,A,B; bool check(int MX){ for (int i = 0; i <=n; ++i) for (int j = 0; j <=n; ++j) dp[i][j]=0; dp[0][0]=1; for(int i=1;i<=n;i++) for(int k=1;k<=i;k++){ int sm=0; for(int j=i;j>=1;j--){ sm+=arr[j]; if(dp[j-1][k-1] && ((MX|sm)==MX)) dp[i][k]=1; } } for(int k=A;k<=B;k++) if(dp[n][k]) return 1; return 0; } bool check2(int MX){ for (int i = 0; i <=n; ++i) dp2[i]=inf; dp2[0]=0; for(int i=0;i<n;i++){ int sm=0; for(int j=i+1;j<=n;j++){ sm+=arr[j]; if((MX|sm)==MX) dp2[j]=min(dp2[j],dp2[i]+1); } } if(A<=dp2[n] && dp2[n]<=B) return 1; return 0; } signed main(){ cin>>n>>A>>B; for (int i = 1; i <=n; ++i) cin>>arr[i]; if(A==1){ int one=1; int ans=(one<<50)-1; for(int b=49;b>=0;b--) if(check2(ans-(one<<b))) ans-=(one<<b); cout<<ans<<endl; return 0; } int one=1; int ans=(one<<44)-1; for(int b=43;b>=0;b--) if(check(ans-(one<<b))) ans-=(one<<b); cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...