Submission #838932

#	Time	Username	Problem	Language	Result	Execution time	Memory
838932		tch1cherin	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	97 ms	440 KiB

sculpture

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

const int BITS = 45;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, A, B;
  cin >> N >> A >> B;
  vector<int> Y(N);
  for (int &v : Y) {
    cin >> v;
  }
  long long mask = (1LL << BITS) - 1;
  for (int bit = BITS - 1; bit >= 0; bit--) {
    mask ^= 1LL << bit;
    bool good;
    if (A == 1) {
      vector<int> dp(N + 1, N + 1);
      dp[0] = 0;
      for (int i = 1; i <= N; i++) {
        long long sum = 0;
        for (int j = i - 1; j >= 0; j--) {
          sum += Y[j];
          if ((sum & mask) == sum) {
            dp[i] = min(dp[i], dp[j] + 1);
          }
        }
      }
      good = dp[N] <= B;
    } else {
      vector<vector<bool>> dp(N + 1, vector<bool>(N + 1, false));
      dp[0][0] = true;
      for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
          long long sum = 0;
          for (int k = i - 1; k >= 0; k--) {
            sum += Y[k];
            if ((sum & mask) == sum) {
              dp[i][j] = dp[i][j] || dp[k][j - 1];
            }
          }
        }
      }
      good = false;
      for (int j = A; j <= B; j++) {
        good = good || dp[N][j];
      }
    }
    if (!good) {
      mask ^= 1LL << bit;
    }
  }
  cout << mask << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29