Submission #970704

#	Time	Username	Problem	Language	Result	Execution time	Memory
970704		kilkuwu	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	168 ms	792 KiB

sculpture

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

const int mxN = 2005;
int N, A, B;
int Y[mxN];
int64_t P[mxN];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::cin >> N >> A >> B;

  for (int i = 1; i <= N; i++) std::cin >> Y[i], P[i] = P[i - 1] + Y[i];

  int64_t ans = (1LL << 61) - 1;

  auto check = [&]() -> bool {
    if (A > 1) {
      std::vector<std::vector<int>> dp(N + 1, std::vector<int>(N + 1));
      dp[0][0] = true;
      for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
          for (int k = i; k >= j; k--) {
            if ((ans | (P[i] - P[k - 1])) == ans) {
              dp[i][j] |= dp[k - 1][j - 1];
            }
          } 
        }
      }

      for (int j = A; j <= B; j++) {
        if (dp[N][j]) return true;
      }
      return false;
    }

    std::vector<int> dp(N + 1);
    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
      dp[i] = 1e9;
      for (int j = i; j >= 1; j--) {
        if ((ans | (P[i] - P[j - 1])) == ans) {
          dp[i] = std::min(dp[i], dp[j - 1] + 1);
        }
      }
    }

    return dp[N] <= B;
  };

  for (int bit = 60; bit >= 0; bit--) {
    ans ^= 1LL << bit;
    dbg(std::bitset<60>(ans), ans);

    if (!check()) {
      dbg("failed bit", bit);
      ans ^= 1LL << bit; 
    } else {
      dbg("success bit", bit);
    }
  }

  std::cout << ans << nl;
}

/*

6 1 3
8 1 2 1 5 4
*/

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