Submission #257882

#	Time	Username	Problem	Language	Result	Execution time	Memory
257882		EntityIT	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	112 ms	512 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_sculptures, min_n_groups, max_n_groups; cin >> n_sculptures >> min_n_groups >> max_n_groups;
  vec<int, 1> years(n_sculptures);
  for (auto& year : years) {
    cin >> year;
  }

  int64_t answer = 0;
  for (int bit = 40; ~bit; --bit) {
    if (min_n_groups == 1) {
      vec<int, 1> distances(n_sculptures + 1, -1); distances[0] = 0;
      queue<int> q; q.emplace(0);
      while (SZ(q)) {
        int u = q.front(); q.pop();
        int64_t sum = 0;
        for (int v = u + 1; v <= n_sculptures; ++v) {
          sum += years[v - 1];
          if (!~distances[v] && ((sum >> bit << bit) | answer) == answer) {
            distances[v] = distances[u] + 1;
            q.emplace(v);
          }
        }
      }
      if (!~distances[n_sculptures] || distances[n_sculptures] > max_n_groups) {
        answer |= static_cast<int64_t>(1) << bit;
      }
    } else {
      vec<bool, 2> f(n_sculptures + 1, max_n_groups + 1);
      f[0][0] = true;
      for (int i = 0; i < n_sculptures; ++i) {
        for (int j = 0; j < max_n_groups; ++j) {
          if (!f[i][j]) {
            continue;
          }
          int64_t sum = 0;
          for (int next_i = i + 1; next_i <= n_sculptures; ++next_i) {
            sum += years[next_i - 1];
            if (((sum >> bit << bit) | answer) == answer) {
              f[next_i][j + 1] = true;
            }
          }
        }
      }
      if (!count(min_n_groups + ALL(f.back()), true)) {
        answer |= static_cast<int64_t>(1) << bit;
      }
    }
  }

  cout << answer << '\n';

  return 0;
}

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