Submission #490823

#TimeUsernameProblemLanguageResultExecution timeMemory
490823RainbowbunnyBali Sculptures (APIO15_sculpture)C++17
100 / 100
107 ms600 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2005; const int INF = 1e9; int n, a, b; long long A[MAXN]; bool dp[MAXN][MAXN]; int f[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> a >> b; for(int i = 1; i <= n; i++) { cin >> A[i]; A[i] += A[i - 1]; } if(n <= 100) { long long ans = 0; for(int bit = 40; bit >= 0; bit--) { for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { dp[i][j] = false; } } dp[0][0] = true; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { for(int k = 1; k <= i; k++) { long long zz = ((A[i] - A[k - 1]) >> bit) << bit; dp[i][j] |= (dp[k - 1][j - 1] & ((zz & ans) == zz)); } } } bool ok = false; for(int i = a; i <= b; i++) { if(dp[n][i]) { ok = true; } } if(!ok) { ans |= (1ll << bit); } } cout << ans << '\n'; } else { long long ans = 0; for(int bit = 40; bit >= 0; bit--) { for(int i = 1; i <= n; i++) { f[i] = INF; } for(int i = 1; i <= n; i++) { for(int j = i; j >= 1; j--) { long long zz = ((A[i] - A[j - 1]) >> bit) << bit; if((zz & ans) == zz) { f[i] = min(f[i], f[j - 1] + 1); } } } if(f[n] > b) { ans |= (1ll << bit); } } 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...