Submission #866298

#TimeUsernameProblemLanguageResultExecution timeMemory
866298Dec0DeddBali Sculptures (APIO15_sculpture)C++14
100 / 100
127 ms15700 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e3+1; const int K = 45; const int INF = 1e9; int dp[N][N]; ll x[N], p[N], n, l, r; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>l>>r; for (int i=1; i<=n; ++i) { cin>>x[i]; p[i]=p[i-1]+x[i]; } ll ans=0, t=0; if (l == 1) { // sol in O(n^2logS) for (int j=K-1; j>=0; --j) { t+=(1ll<<j); for (int i=0; i<=n; ++i) dp[i][0]=INF; dp[0][0]=0; for (int i=1; i<=n; ++i) { for (int x=i; x>=1; --x) { ll q=p[i]-p[x-1], tmp=q&t; if ((tmp|ans) == ans) dp[i][0]=min(dp[i][0], dp[x-1][0]+1); } } if (dp[n][0] > r) ans^=(1ll<<j); } } else { // sol in O(n^3 logS) for (int j=K-1; j>=0; --j) { t+=(1ll<<j); for (int i=0; i<=n; ++i) { for (int l=0; l<=n; ++l) dp[i][l]=false; } dp[0][0]=1; for (int i=1; i<=n; ++i) { for (int l=1; l<=n; ++l) { for (int x=i; x>=1; --x) { ll q=p[i]-p[x-1], tmp=q&t; if ((tmp|ans) == ans) dp[i][l]|=dp[x-1][l-1]; } } } bool k=false; for (int i=l; i<=r; ++i) k|=dp[n][i]; if (!k) ans^=(1ll<<j); } } cout<<ans<<"\n"; }
#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...