結果
問題 |
No.3303 Heal Slimes 2
|
ユーザー |
|
提出日時 | 2025-10-05 15:43:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,715 ms / 4,000 ms |
コード長 | 8,013 bytes |
コンパイル時間 | 3,198 ms |
コンパイル使用メモリ | 293,572 KB |
実行使用メモリ | 11,416 KB |
最終ジャッジ日時 | 2025-10-06 12:47:48 |
合計ジャッジ時間 | 29,548 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class F> class y_combinator { F f; public: y_combinator(F&& f) : f(std::forward<F>(f)) {} template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); } }; using ll = long long; using ld = long double; using u64 = uint64_t; using vi = vector<int>; using vl = vector<ll>; using pii = pair<int, int>; using pll = pair<ll, ll>; template <class T, class U = std::less<T>> using prique = std::priority_queue<T, std::vector<T>, U>; inline constexpr int popcnt(u64 x) noexcept { return __builtin_popcountll(x); } inline ll floor_div(ll a, ll b) noexcept { return a / b - (a % b && (a ^ b) < 0); } inline ll ceil_div(ll a, ll b) noexcept { return floor_div(a + b - 1, b); } template <class T> bool chmin(T& x, const T& y) noexcept { return (x > y ? x = y, true : false); } template <class T> bool chmax(T& x, const T& y) noexcept { return (x < y ? x = y, true : false); } template <class T> void dedup(std::vector<T>& v) { std::sort(std::begin(v), std::end(v)), v.erase(std::unique(std::begin(v), std::end(v)), std::end(v)); } template <class F> ll bisect(ll ok, ll ng, const F& f) { while (abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } template <class F> ld bisect_real(ld ok, ld ng, const F& f, int iter = 80) { while (iter--) { ld mid = (ok + ng) / 2.; (f(mid) ? ok : ng) = mid; } return ok; } inline void SCAN() {} template <class H, class... T> inline void SCAN(H& h, T&... t) { std::cin >> h, SCAN(t...); } #define INT(...) \ int __VA_ARGS__; \ SCAN(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ SCAN(__VA_ARGS__) #define LD(...) \ long double __VA_ARGS__; \ SCAN(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ SCAN(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ SCAN(__VA_ARGS__) #define VEC(type, name, size) \ std::vector<type> name(size); \ for (int i = 0; i < (int)size; i++) SCAN(name[i]); #define VV(type, name, h, w) \ std::vector<std::vector<type>> name(h, std::vector<type>(w)); \ for (int i = 0; i < (int)h; i++) \ for (int j = 0; j < (int)w; j++) SCAN(name[i][j]); #define overload4(a, b, c, d, e, ...) e #define rep1(a) for (long long _i = 0; _i < (a); _i++) #define rep2(i, a) for (long long i = 0; i < (a); i++) #define rep3(i, a, b) for (long long i = (a); i < (b); i++) #define rep4(i, a, b, c) for (long long i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep(i, a, b, c) for (long long i = (a); i > (b); i += (c)) #define all(x) std::begin(x), std::end(x) #define rall(x) std::rbegin(x), std::rend(x) #define len(x) (long long)(size(x)) #define pb push_back #ifndef LOCAL #define debug(...) #endif #line 2 "dp/golden-section-search.hpp" #include <cassert> #include <functional> #include <utility> using namespace std; namespace golden_section_search_impl { using i64 = long long; template <typename T, bool get_min = true> pair<i64, T> golden_section_search(const function<T(i64)>& f, i64 min, i64 max) { assert(min <= max); i64 a = min - 1, x, b; { i64 s = 1, t = 2; while (t < max - min + 2) swap(s += t, t); x = a + t - s, b = a + t; } T fx = f(x), fy; while (a + b != 2 * x) { i64 y = a + b - x; if (max < y || (fy = f(y), get_min ? fx < fy : fx > fy)) { b = a; a = y; } else { a = x; x = y; fx = fy; } } return {x, fx}; } } // namespace golden_section_search_impl using golden_section_search_impl::golden_section_search; /* @brief 黄金分割探索 */ #include <atcoder/segtree> template <class T = long long> class Compressor { private: std::vector<T> cc; bool sorted; public: Compressor() : sorted(false) {} Compressor(const std::vector<T>& a) { for (auto x : a) cc.push_back(x); build(); } void add(const T& x) { cc.push_back(x); sorted = false; } T operator[](int i) const { assert(sorted); return cc[i]; } int operator()(const T& x) const { assert(sorted); return lower_bound(begin(cc), end(cc), x) - begin(cc); } int size() const { assert(sorted); return cc.size(); } void build() { sort(begin(cc), end(cc)); cc.erase(unique(begin(cc), end(cc)), end(cc)); sorted = true; } static std::vector<int> compressed(const std::vector<T>& a) { Compressor c(a); std::vector<int> res(a.size()); for (int i = 0; i < (int)a.size(); i++) res[i] = c(a[i]); return res; } }; template <class T> class FixedSet { public: struct S { T sum; int count; }; static S op(S a, S b) { return S{a.sum + b.sum, a.count + b.count}; } static S e() { return S{T{}, 0}; } using STree = atcoder::segtree<S, op, e>; STree d; Compressor<T> cc; size_t sz; int index(const T& x) { int p = cc(x); assert(0 <= p && p < cc.size() && cc[p] == x); return p; } FixedSet() {} FixedSet(const std::vector<T>& A) { cc = Compressor<T>(A); d = STree(cc.size()); sz = 0; } void add(const T& x, int c = 1) { int p = index(x); S pv = d.get(p); sz -= pv.count; int cnt = std::max(0, pv.count + c); d.set(p, S{x * cnt, cnt}); sz += cnt; } T top_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int l = d.min_left(cc.size(), f) - 1; S res = d.prod(l, cc.size()); T sum = res.sum - cc[l] * (res.count - k); return sum; } T bottom_k_sum(int k) { if (k == 0) return T{}; assert(k <= (int)size()); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); S res = d.prod(0, r); T sum = res.sum + cc[r] * (k - res.count); return sum; } T kth_smallest(int k) { assert(0 < k && k <= sz); const auto f = [&](S x) { return x.count < k; }; int r = d.max_right(0, f); return cc[r]; } T kth_largest(int k) { return kth_smallest(sz - k + 1); } size_t size() const { return sz; } bool empty() const { return size() == 0; } int count(const T& x) { int pos = index(x); return d.get(pos).count; } T sum() const { return d.all_prod().sum; } }; void run_case() { LL(N, K, D); VEC(ll, H, N); vector<ll> A; rep(i, N) { A.pb(H[i]); } A.push_back(1e18); FixedSet<ll> ST(A); ll ans = 1e18; rep(i, N) { if (i < K - 1) { ST.add(H[i], 1); } else { ST.add(H[i], 1); auto check = [&](ll t) -> ll { ll sum = 0; { int id = ST.cc(t); auto S = ST.d.prod(0, id); sum += t * S.count - ST.bottom_k_sum(S.count); } { int id = ST.cc(t + D); auto S = ST.d.prod(id, ST.cc.size()); sum += ST.top_k_sum(S.count) - (t + D) * S.count; } return sum; }; auto res = golden_section_search<ll>(check, 0, 1e9); chmin(ans, res.second); ST.add(H[i - K + 1], -1); } } cout << ans << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::fixed(std::cout).precision(16); int T = 1; while (T--) run_case(); return 0; }