:heavy_check_mark: test/aoj_2580.test.cpp

Back to top page

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580"

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>

#include "utility/literals.cpp"
#include "utility/make/vector.cpp"
#include "utility/make/fix_point.cpp"
#include "algorithm/monotone_minima.cpp"

int main() {
  size_t n, m, d;
  intmax_t x;
  scanf("%zu %zu %zu %jd", &n, &m, &d, &x);

  std::vector<intmax_t> p(n);
  for (auto& pi: p) scanf("%jd", &pi);

  std::vector<intmax_t> q(m);
  for (auto& qi: q) {
    intmax_t a, b;
    scanf("%jd %jd", &a, &b);
    qi = a - std::abs(b);
  }

  intmax_t const inf = 1e18;
  intmax_t res = inf;
  auto dp = make_vector({n}, inf);
  dp[0] = 0;
  for (size_t dd = 0; dd < d; ++dd) {
    std::vector<intmax_t> w(n+1, 0);
    w[0] = m;
    for (auto const& qi: q) {
      size_t i = std::upper_bound(p.begin(), p.end(), qi) - p.begin();
      --w[i];
    }
    for (size_t i = 1; i <= n; ++i) w[i] += w[i-1];

    auto tmp = make_vector({n}, inf);

    auto f = [&](size_t i, size_t j) -> intmax_t {
      if (!(j < i)) return inf;
      return dp[j] + w[j] * (p[i]-p[j]);
    };
    auto prev = monotone_minima(f, n, n);

    for (size_t i = 0; i < n; ++i)
      tmp[i] = f(i, prev[i]);

    dp = std::move(tmp);
    res = std::min(res, dp[n-1]);
    for (auto& qi: q) qi += x;
  }

  printf("%jd\n", res);
}

#line 1 "test/aoj_2580.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580"

#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>

#line 1 "utility/literals.cpp"



/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#include <cstddef>
#line 11 "utility/literals.cpp"

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

constexpr int8_t   operator ""_i8(unsigned long long n)  { return n; }
constexpr int16_t  operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t  operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t  operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t  operator ""_u8(unsigned long long n)  { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }


#line 1 "utility/make/vector.cpp"



/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */

#line 10 "utility/make/vector.cpp"
#include <type_traits>
#line 12 "utility/make/vector.cpp"

namespace detail {
  template <typename Tp, size_t Nb>
  auto make_vector(std::vector<size_t>& sizes, Tp const& x) {
    if constexpr (Nb == 1) {
      return std::vector(sizes[0], x);
    } else {
      size_t size = sizes[Nb-1];
      sizes.pop_back();
      return std::vector(size, make_vector<Tp, Nb-1>(sizes, x));
    }
  }
}  // detail::

template <typename Tp, size_t Nb>
auto make_vector(size_t const(&sizes)[Nb], Tp const& x = Tp()) {
  std::vector<size_t> s(Nb);
  for (size_t i = 0; i < Nb; ++i) s[i] = sizes[Nb-i-1];
  return detail::make_vector<Tp, Nb>(s, x);
}


#line 1 "utility/make/fix_point.cpp"
/**
 * @brief ラムダ式の再帰
 * @author えびちゃん
 */

#ifndef H_make_fix_point
#define H_make_fix_point

#line 10 "utility/make/fix_point.cpp"

template <typename Fn>
class fix_point: Fn {
public:
  explicit constexpr fix_point(Fn&& f) noexcept: Fn(std::forward<Fn>(f)) {}

  template <typename... Args>
  constexpr decltype(auto) operator ()(Args&&... args) const {
    return Fn::operator ()(*this, std::forward<Args>(args)...);
  }
};

template <typename Fn>
static inline constexpr decltype(auto) make_fix_point(Fn&& f) noexcept {
  return fix_point<Fn>{std::forward<Fn>(f)};
}

#endif  /* !defined(H_make_fix_point) */
#line 1 "algorithm/monotone_minima.cpp"



/**
 * @brief monotone minima
 * @author えびちゃん
 */

#line 12 "algorithm/monotone_minima.cpp"

#line 1 "utility/make/fix_point.cpp"
/**
 * @brief ラムダ式の再帰
 * @author えびちゃん
 */

#ifndef H_make_fix_point
#define H_make_fix_point

#line 10 "utility/make/fix_point.cpp"

template <typename Fn>
class fix_point: Fn {
public:
  explicit constexpr fix_point(Fn&& f) noexcept: Fn(std::forward<Fn>(f)) {}

  template <typename... Args>
  constexpr decltype(auto) operator ()(Args&&... args) const {
    return Fn::operator ()(*this, std::forward<Args>(args)...);
  }
};

template <typename Fn>
static inline constexpr decltype(auto) make_fix_point(Fn&& f) noexcept {
  return fix_point<Fn>{std::forward<Fn>(f)};
}

#endif  /* !defined(H_make_fix_point) */
#line 14 "algorithm/monotone_minima.cpp"

template <typename Fn>
auto monotone_minima(Fn&& f, size_t h, size_t w) {
  using value_type = decltype(f(h, w));
  std::vector<size_t> res(h);

  make_fix_point([&](auto dfs, size_t hl, size_t hu, size_t wl, size_t wu) -> void {
      if (hl >= hu) return;
      size_t hm = (hl+hu) >> 1;
      value_type min = f(hm, wl);
      res[hm] = wl;
      for (size_t j = wl+1; j < wu; ++j) {
        value_type cur = f(hm, j);
        if (cur < min) {
          min = std::move(cur);
          res[hm] = j;
        }
      }
      if (hl == hm) return;
      dfs(hl, hm, wl, res[hm]+1);
      dfs(hm+1, hu, res[hm], wu);
  })(0, h, 0, w);
  return res;
}


#line 14 "test/aoj_2580.test.cpp"

int main() {
  size_t n, m, d;
  intmax_t x;
  scanf("%zu %zu %zu %jd", &n, &m, &d, &x);

  std::vector<intmax_t> p(n);
  for (auto& pi: p) scanf("%jd", &pi);

  std::vector<intmax_t> q(m);
  for (auto& qi: q) {
    intmax_t a, b;
    scanf("%jd %jd", &a, &b);
    qi = a - std::abs(b);
  }

  intmax_t const inf = 1e18;
  intmax_t res = inf;
  auto dp = make_vector({n}, inf);
  dp[0] = 0;
  for (size_t dd = 0; dd < d; ++dd) {
    std::vector<intmax_t> w(n+1, 0);
    w[0] = m;
    for (auto const& qi: q) {
      size_t i = std::upper_bound(p.begin(), p.end(), qi) - p.begin();
      --w[i];
    }
    for (size_t i = 1; i <= n; ++i) w[i] += w[i-1];

    auto tmp = make_vector({n}, inf);

    auto f = [&](size_t i, size_t j) -> intmax_t {
      if (!(j < i)) return inf;
      return dp[j] + w[j] * (p[i]-p[j]);
    };
    auto prev = monotone_minima(f, n, n);

    for (size_t i = 0; i < n; ++i)
      tmp[i] = f(i, prev[i]);

    dp = std::move(tmp);
    res = std::min(res, dp[n-1]);
    for (auto& qi: q) qi += x;
  }

  printf("%jd\n", res);
}

Back to top page