Submission #1340527

#TimeUsernameProblemLanguageResultExecution timeMemory
1340527ramzialoulouBali Sculptures (APIO15_sculpture)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
 
using namespace std;

const int N = 109;
const int inf = int(1e9);
int a[N];
int64_t sum[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, A, B;
  cin >> n >> A >> B;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i];
  }
  int64_t ans = 0;
  int mn_msb = inf;
  vector<int> dp(n + 1, inf);
  for (int bit = 59; bit >= 0; bit--) {
    vector ndp(n + 1, vector<int>(n + 1, inf));
    ndp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      for (int cnt = 1; cnt <= B; cnt++) {
        for (int j = 0; j < i; j++) {
          auto s = sum[i] - sum[j];
          s &= (int64_t(1) << (bit + 2)) - 1;
          int msb = 63 - __builtin_clzll(s);
          ndp[i][cnt] = min(ndp[i][cnt], max(msb, ndp[j][cnt - 1]));
        }
      }
    }
    int n_mn_msb = inf;
    for (int cnt = A; cnt <= B; cnt++) {
      if (dp[cnt] == mn_msb) {
        n_mn_msb = min(mn_msb, ndp[n][cnt]);
      }
    }
    if (n_mn_msb == bit) {
      ans |= int64_t(1) << bit;
      mn_msb = bit;
      swap(dp, ndp[n]);
    }
  }
  cout << ans << '\n';
  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...