結果

問題 No.861 ケーキカット
ユーザー ngtkana
提出日時 2019-08-09 22:59:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,733 bytes
コンパイル時間 2,440 ms
コンパイル使用メモリ 207,036 KB
最終ジャッジ日時 2025-01-07 11:32:07
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 3
other TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define LOCAL
using std::to_string;
auto to_string(std::string s) -> std::string {
  return '"' + s + '"';
}
auto to_string(char c) -> std::string {
  return "'" + std::string{c} + "'";
}
auto to_string(const char* s) -> std::string {
  return to_string((std::string) s);
}
auto to_string(bool b) -> std::string {
  return (b ? "true" : "false");
}
template <typename T, typename U>
auto to_string(std::pair<T, U> p) -> std::string {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <size_t N>
auto to_string(std::bitset<N> bs) -> std::string {
  std::string res{};
  for (size_t i = 0; i < N; i++)
    res.insert(res.begin(), bs.test(i) ? '1' : '0');
  return res;
}
template <typename T>
auto to_string(T v) -> std::string {
  bool flg = false;
  std::string res = "{";
  for (auto const&x : v) {
    if (flg) res += ", ";
    else flg = true;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<typename T>
class fixed_point : T {
  public:
    explicit constexpr fixed_point (T&& t) noexcept
      : T(std::forward<T>(t)) {}
    template<typename... Args>
    constexpr decltype(auto) operator()(Args&&... args) const
      {return T::operator()(*this, std::forward<Args>(args)...);}
};
template<typename T>
static inline constexpr decltype(auto) fix (T&& t) noexcept {
  return fixed_point<T>{std::forward<T>(t)};
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  constexpr int n = 5, N = 25, bsm = 1 << N;
  auto a = std::vector<std::vector<int>>(n, std::vector<int>(n));
  for (auto& v : a) for (auto& x : v) std::cin >> x;
  int di[4] = {-1, +1, 0, 0};
  int dj[4] = {0, 0, -1, +1};
  auto encode = [&] (int i, int j) {
    assert(0 <= i && i < n);
    assert(0 <= j && j < n);
    return i * n + j;
  };
  auto decode = [&] (int pos) {
    assert(0 <= pos && pos < N);
    return std::pair<int, int>{pos / n, pos % n};
  };
  // Access the j-th bit.
  auto at = [](unsigned x, size_t j) -> bool {
    return (x >> j) & 1;
  };
  auto check = [&] (int bs) -> bool {
    int ckd = 0;
    auto dfs = fix ([&](auto dfs, int crr) -> void {
      assert(0 <= crr && crr < N);
      ckd |= 1 << crr;
      auto [cri, crj] = decode(crr);
      for (int k = 0; k < 4; k++) {
        int nxi = cri + di[k];
        int nxj = crj + dj[k];
        if (nxi < 0 || n <= nxi || nxj < 0 || n <= nxj) {
          continue;
        }
        auto nxt = encode(nxi, nxj);
        if (at(ckd, nxt) || !at(bs, nxt)) {
          continue;
        }
        dfs(nxt);
      }
    });
    if (bs == 0) return true;
    for (int i = 0; i < N; i++) {
      if (at(bs, i)) {
        dfs(i);
        break;
      }
    }
    return bs == ckd;
  };
  constexpr long long inf = 1LL << 60;
  auto acm = [&] (int bs) -> long long{
    long long ret = 0;
    for (int pos = 0; pos < N; pos++) {
      auto [i, j] = decode(pos);
      if (at(bs, pos)) ret += a.at(i).at(j);
    }
    return ret;
  };
  long long sum = acm(bsm - 1);
  auto cal = [&] (int bs) -> long long {
    int cs = (bsm - 1) ^ bs;
    assert(!(bs & cs));
    assert((bs | cs) == (bsm - 1));
    if (!check(bs) || !check(cs)) return inf;
    if (bs > cs) return inf;
    auto ret = std::abs(sum - 2 * acm(bs));
    return ret;
  };
  long long ret = inf;
  for (int bs = 1; bs < bsm - 1; bs++) {
    ret = std::min(ret, cal(bs));
  }
  std::cout << ret << std::endl;
  return 0;
}
0