結果

問題 No.913 木の燃やし方
ユーザー noshi91noshi91
提出日時 2019-10-18 22:23:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 594 ms / 3,000 ms
コード長 6,722 bytes
コンパイル時間 1,070 ms
コンパイル使用メモリ 87,944 KB
実行使用メモリ 52,196 KB
最終ジャッジ日時 2023-09-07 23:59:26
合計ジャッジ時間 21,150 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 9 ms
4,380 KB
testcase_04 AC 9 ms
4,376 KB
testcase_05 AC 9 ms
4,380 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 4 ms
4,380 KB
testcase_08 AC 569 ms
50,048 KB
testcase_09 AC 551 ms
48,172 KB
testcase_10 AC 552 ms
48,432 KB
testcase_11 AC 558 ms
48,960 KB
testcase_12 AC 590 ms
51,880 KB
testcase_13 AC 571 ms
50,384 KB
testcase_14 AC 550 ms
48,096 KB
testcase_15 AC 545 ms
47,988 KB
testcase_16 AC 509 ms
50,192 KB
testcase_17 AC 487 ms
48,152 KB
testcase_18 AC 482 ms
48,204 KB
testcase_19 AC 530 ms
51,808 KB
testcase_20 AC 525 ms
52,196 KB
testcase_21 AC 556 ms
51,748 KB
testcase_22 AC 537 ms
51,880 KB
testcase_23 AC 513 ms
51,832 KB
testcase_24 AC 483 ms
51,940 KB
testcase_25 AC 473 ms
51,912 KB
testcase_26 AC 592 ms
51,904 KB
testcase_27 AC 594 ms
51,796 KB
testcase_28 AC 569 ms
52,004 KB
testcase_29 AC 552 ms
51,936 KB
testcase_30 AC 553 ms
51,956 KB
testcase_31 AC 577 ms
51,784 KB
testcase_32 AC 586 ms
52,008 KB
testcase_33 AC 589 ms
51,848 KB
testcase_34 AC 522 ms
51,812 KB
testcase_35 AC 516 ms
51,872 KB
testcase_36 AC 490 ms
51,892 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0