Submission #766343

#TimeUsernameProblemLanguageResultExecution timeMemory
766343linkretBali Sculptures (APIO15_sculpture)C++14
100 / 100
153 ms4320 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int N = 2020; int n, a, b; ll mask = (1ll << 61) - 1; ll arr[N]; bool dp[N][N]; ll dp1[N]; /* 6 1 3 8 1 2 1 5 4 */ void solve() { for (ll bit = 60; bit >= 0; bit--) { mask ^= (1ll << bit); memset(dp, 0, sizeof dp); dp[0][0] = 1; for (int i = 1; i <= n; i++) for (int cnt = 1; cnt <= n; cnt++) { ll sum = 0; for (int j = i; j >= 1; j--) { sum += arr[j]; if ((sum | mask) == mask) dp[i][cnt] |= dp[j - 1][cnt - 1]; } } bool ok = false; for (int i = a; i <= b; i++) ok |= dp[n][i]; if (!ok) mask ^= (1ll << bit); } } void solve_1() { for (ll bit = 60; bit >= 0; bit--) { mask ^= (1ll << bit); for (int i = 1; i <= n; i++) { dp1[i] = 1e9; ll sum = 0; for (int j = i; j >= 1; j--) { sum += arr[j]; if ((sum | mask) == mask) dp1[i] = min(dp1[i], 1 + dp1[j - 1]); } } if (dp1[n] > b) mask ^= (1ll << bit); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> a >> b; for (ll i = 1; i <= n; i++) cin >> arr[i]; if (a == 1) solve_1(); else solve(); cout << mask << 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...