Submission #154249

#	Time	Username	Problem	Language	Result	Execution time	Memory
154249		nthoang	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	138 ms	504 KiB

sculpture

#include <bits/stdc++.h>

#ifdef LOCAL
#include "/Users/nth842002/Library/debug.h"
#endif

using namespace std;

const int N = 2222;
const int LOG = 45;
const int INF = (int) 1e9 + 7;

int n, A, B;
long long a[N];
long long p2[LOG + 10];
long long prefix;

inline bool Check(long long sum) {
  sum = p2[LOG] - 1 - sum;
  return (sum & prefix) == prefix;
}

void Solve1() {
  long long ans = 0;
  for (int bits = LOG - 1; bits >= 0; bits--) {
    prefix += p2[bits];
    vector<int> f(n + 1, INF);
    f[0] = 0;
    for (int i = 0; i < n; i++) {
      if (f[i] == INF) {
        continue;
      }
      for (int j = i; j < n; j++) {
        if (Check(a[j] - (i == 0 ? 0 : a[i - 1]))) {
          f[j + 1] = min(f[j + 1], f[i] + 1);
        }
      }
    }
    if (f[n] > B) {
      prefix -= p2[bits];
      ans += p2[bits];
    }
  }
  cout << ans << '\n';
}

void Solve2() {
  long long ans = 0;
  for (int bits = LOG - 1; bits >= 0; bits--) {
    prefix += p2[bits];
    vector<vector<bool>> f(n + 1, vector<bool>(n + 1));
    f[0][0] = true;
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < B; k++) {
        if (!f[i][k]) {
          continue;
        }
        for (int j = i; j < n; j++) {
          if (Check(a[j] - (i == 0 ? 0 : a[i - 1]))) {
            f[j + 1][k + 1] = true;
          }
        }
      }
    }
    bool exist = false;
    for (int k = A; k <= B; k++) {
      if (f[n][k]) {
        exist = true;
        break;
      }
    }
    if (not exist) {
      prefix -= p2[bits];
      ans += p2[bits];
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> A >> B;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  p2[0] = 1;
  for (int i = 1; i <= LOG; i++) {
    p2[i] = p2[i - 1] + p2[i - 1];
  }
  if (A == 1) {
    Solve1();
  } else {
    Solve2();
  }
  return 0;
}

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