oj.uz

답안 #396555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396555 2021-04-30T09:50:06 Z Cyanmond Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 204 KB 
#include "bits/stdc++.h"
#pragma region cscpptemp
// require at least C++17 to compile
using llint = long long int;
template <class T>
using Heap = std::priority_queue<T>;
template <class T>
using RevHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// ex. for (const int i : range(a, b)) ... loop [a, b)
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class range {
  struct range_iterator {
    T itr;
    constexpr range_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const range_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr range(const T first_, const T last_) noexcept
      : first(first_), last(last_) {}
  constexpr range_iterator begin() const noexcept { return first; }
  constexpr range_iterator end() const noexcept { return last; }

 private:
  const range_iterator first, last;
};

// ex. for (const int i : range(a, b)) ... revloop [a, b]
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class revrange {
  struct revrange_iterator {
    T itr;
    constexpr revrange_iterator(const int pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator!=(const revrange_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr T operator*() const noexcept { return itr; }
  };

 public:
  constexpr revrange(const T first_, const T last_) noexcept
      : first(first_), last(last_ - 1) {}
  constexpr revrange_iterator begin() const noexcept { return first; }
  constexpr revrange_iterator end() const noexcept { return last; }

 private:
  const revrange_iterator first, last;
};

// ex. rec_lambda([](auto&& f, int n) -> int {return n < 1 ? 1 : f(--n); })
template <class F>
class rec_lambda {
 public:
  constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }

 private:
  F f;
};

// ex. const int N = read()
struct read {
  template <class T>
  [[nodiscard]] operator T() {
    T ret;
    std::cin >> ret;
    return ret;
  }
};

// ex. chmax(a, b) ... a = max(a, b)
template <class T>
constexpr void chmax(T& a, const T b) noexcept {
  if (a < b) a = b;
}
template <class T>
constexpr void chmin(T& a, const T b) noexcept {
  if (a > b) a = b;
}

// ex. ceildiv(a, b) ... ceil(a / b)
template <class T, class = std::enable_if_t<std::is_integral_v<T>>>
constexpr T ceildiv(const T dividend, const T divisor) {
  return (dividend + divisor - 1) / divisor;
}

// ex. mk_vec(a, b, c, v) ... 3D vector size: [a][b][c] init value: v
template <class T>
auto mk_vec(const int n, const T value) {
  return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const int n, Args... args) {
  return std::vector(n, mk_vec(args...));
}
#pragma endregion

int main() {
  const int N = read(), A = read(), B = read();
  std::vector<llint> Y(N);
  for (auto& el : Y) el = read();

  std::vector<llint> R(N + 1);
  R[0] = 0ll;
  for (const int i : range(0, N)) R[i + 1] = R[i] + Y[i];

  llint ans = 0ll, wal = 0ll;
  for (const int bit : revrange(50, 0)) {
    if (A == 1) {
      std::vector<int> DP(N + 1, 1 << 30);
      DP[0] = 0;
      for (const int i : range(0, N))
        for (const int j : range(0, i)) {
          if (((R[i + 1] - R[j]) & wal + (1ll << bit)) == 0)
            chmin(DP[i + 1], DP[j] + 1);
        }
      if (not(DP[N] <= B))
        ans += 1ll << bit;
      else
        wal += 1ll << bit;
    } else {
      std::vector DP(N + 1, std::vector(N + 1, false));
      DP[0][0] = true;
      for (const int i : range(0, N))
        for (const int j : range(0, i))
          for (const int k : range(1, i + 1)) {
            if (DP[i + 1][k]) continue;
            if (((R[i + 1] - R[j]) & (wal + (1ll << bit))) == 0)
              DP[i + 1][k] = DP[j][k - 1];
          }
      if (std::all_of(DP[N].begin() + A, DP[N].begin() + B + 1,
                      [](bool v) { return not v; }))
        ans += 1ll << bit;
      else
        wal += 1ll << bit;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

Compilation message

sculpture.cpp:2: warning: ignoring #pragma region cscpptemp [-Wunknown-pragmas]
    2 | #pragma region cscpptemp
      | 
sculpture.cpp:105: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
  105 | #pragma endregion
      | 
sculpture.cpp: In function 'int main()':
sculpture.cpp:123:40: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  123 |           if (((R[i + 1] - R[j]) & wal + (1ll << bit)) == 0)
      |                                    ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -