Bundle
Copy
#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);
}