結果

問題 No.913 木の燃やし方
ユーザー noshi91
提出日時 2019-10-18 22:23:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 592 ms / 3,000 ms
コード長 6,722 bytes
コンパイル時間 994 ms
コンパイル使用メモリ 88,440 KB
実行使用メモリ 52,148 KB
最終ジャッジ日時 2024-06-25 17:15:21
合計ジャッジ時間 20,100 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
う　し　た　ぷ　に　き　あ　く　ん　笑
*/
//#define NDEBUG
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>
namespace n91 {
using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
struct rep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr rep(const usize f, const usize l) noexcept
      : f(std::min(f, l)), l(l) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
struct revrep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr revrep(const usize f, const usize l) noexcept
      : f(l - 1), l(std::min(f, l) - 1) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) noexcept {
  return a < b ? b - a : a - b;
}
template <class T> void chmin(T &a, const T &b) noexcept {
  if (b < a)
    a = b;
}
template <class T> void chmax(T &a, const T &b) noexcept {
  if (a < b)
    a = b;
}
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}
} // namespace n91
#include <numeric>
#include <vector>
template <class Compare>
std::vector<std::size_t> smawk(const std::size_t rows,
                               std::vector<std::size_t> &&columns,
                               const Compare &comp) {
  using size_type = std::size_t;
  std::vector<size_type> ret(rows);
  std::vector<std::vector<size_type>> index;
  index.push_back(std::move(columns));
  size_type step = static_cast<size_type>(1);
  while (step <= rows) {
    size_type pos = rows;
    std::vector<size_type> stack;
    for (const size_type i : index.back()) {
      while (pos != rows && comp(pos, i, stack.back())) {
        stack.pop_back();
        pos += step;
      }
      if (pos >= step) {
        stack.push_back(i);
        pos -= step;
      }
    }
    index.push_back(std::move(stack));
    step *= static_cast<size_type>(2);
  }
  while (step != static_cast<size_type>(1)) {
    step /= static_cast<size_type>(2);
    typename std::vector<size_type>::const_iterator itr = index.back().cbegin();
    for (size_type i = rows - step;; i -= step + step) {
      const size_type end = i >= step ? ret[i - step] : index.back().back();
      ret[i] = end;
      while (*itr != end) {
        if (comp(i, *itr, ret[i])) {
          ret[i] = *itr;
        }
        ++itr;
      }
      if (i < step * static_cast<size_type>(2)) {
        break;
      }
    }
    index.pop_back();
  }
  return ret;
}
template <class Compare>
std::vector<std::size_t> smawk_increasing(const std::size_t rows,
                                          const std::size_t columns,
                                          const Compare &comp) {
  using size_type = std::size_t;
  std::vector<size_type> index(columns);
  std::iota(index.rbegin(), index.rend(), static_cast<size_type>(0));
  return smawk(rows, std::move(index), comp);
}
template <class Compare>
std::vector<std::size_t> smawk_decreasing(const std::size_t rows,
                                          const std::size_t columns,
                                          const Compare &comp) {
  using size_type = std::size_t;
  std::vector<size_type> index(columns);
  std::iota(index.begin(), index.end(), static_cast<size_type>(0));
  return smawk(rows, std::move(index), comp);
}
#include <algorithm>
#include <iostream>
#include <limits>
#include <utility>
namespace n91 {
void main_() {
  static constexpr i64 Inf = std::numeric_limits<i64>::max();
  const usize n{scan<usize>()};
  std::vector<i64> a(n);
  for (auto &e : a) {
    std::cin >> e;
  }
  std::vector<i64> cumsum(n + 1);
  for (const auto i : rep(0, n)) {
    cumsum[i + 1] = cumsum[i] + a[i];
  }
  const auto ushi_one = [&](const usize l, const usize r) {
    return cumsum[r] - cumsum[l] +
           static_cast<i64>(r - l) * static_cast<i64>(r - l);
  };
  std::vector<std::vector<i64>> dpv(n + 1), dph(n + 1);
  std::vector<i64> ans(n);
  const auto solve = [&](const auto &solve, const usize ll, const usize rr) {
    if (rr - ll == 1) {
      return;
    }
    const usize mid = (ll + rr) / 2;
    // calc v
    {
      dpv[mid].resize(mid - ll);
      i64 temp = ll == 0 ? Inf : dph[ll][mid - ll];
      usize dpit = mid - ll;
      const auto wrap_ushi = [&](const usize i, const usize j) {
        return ushi_one(ll + i, mid + j);
      };
      const auto comp = [&](const usize i, const usize j, const usize k) {
        return wrap_ushi(i, j) < wrap_ushi(i, k);
      };
      usize rit = 0;
      for (const auto e : smawk_increasing(mid - ll, rr - mid, comp)) {
        --dpit;
        chmin(temp, wrap_ushi(rit, e));
        if (rr != n + 1) {
          chmin(temp, dpv[rr][rr - mid + dpit]);
        }
        dpv[mid][dpit] = temp;
        ++rit;
      }
    }
    // clac h
    {
      dph[mid].resize(rr - mid);
      i64 temp = rr == n + 1 ? Inf : dpv[rr][rr - mid];
      usize dpit = rr - mid;
      const auto wrap_ushi = [&](const usize i, const usize j) {
        return ushi_one(mid - j - 1, rr - i - 1);
      };
      const auto comp = [&](const usize i, const usize j, const usize k) {
        return wrap_ushi(i, j) < wrap_ushi(i, k);
      };
      usize rit = 0;
      for (const auto e : smawk_increasing(rr - mid, mid - ll, comp)) {
        --dpit;
        chmin(temp, wrap_ushi(rit, e));
        if (ll != 0) {
          chmin(temp, dph[ll][mid - ll + dpit]);
        }
        dph[mid][dpit] = temp;
        ++rit;
      }
    }
    ans[mid - 1] = dph[mid][0];
    solve(solve, ll, mid);
    solve(solve, mid, rr);
  };
  solve(solve, 0, n + 1);
  for (const auto e : ans) {
    std::cout << e << std::endl;
  }
}
} // namespace n91
int main() {
  n91::main_();
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0