結果

問題 No.3303 Heal Slimes 2
コンテスト
ユーザー Kude
提出日時 2025-10-05 14:55:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 63 ms / 4,000 ms
コード長 3,698 bytes
コンパイル時間 3,249 ms
コンパイル使用メモリ 313,484 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-21 10:22:19
合計ジャッジ時間 5,790 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template <class T, class Comp = less<T>>
struct erasable_priority_queue {
  priority_queue<T, vector<T>, Comp> q, q_erase;
  void push(T x) { q.push(move(x)); }
  template <class... Args>
  void emplace(Args&&... args) {
    q.emplace(forward<Args>(args)...);
  }
  void erase(T x) { q_erase.push(move(x)); }
  decltype(auto) top() {
    assert(!empty());
    expose_top();
    return q.top();
  }
  void pop() {
    assert(!empty());
    expose_top();
    q.pop();
  }
  int size() { return int(q.size()) - int(q_erase.size()); }
  bool empty() { return !size(); }
  void expose_top() {
    while (!q_erase.empty() && q_erase.top() == q.top()) {
      q_erase.pop();
      q.pop();
    }
  }
};


template<class T=long long>
struct SlopeTrick {
    static constexpr T INF = std::numeric_limits<T>::max() / 3;
    T min_f = 0;

    // acutual value of x in L is ADD_add_L(x) = x + add_L
    T add_L = 0, add_R = 0;
    erasable_priority_queue<T> L;
    erasable_priority_queue<T, std::greater<>> R;

    T top_L() { return L.empty() ? -INF : L.top() + add_L; }
    T top_R() { return R.empty() ? +INF : R.top() + add_R; }
    void push_L(T x) { L.push(x - add_L); }
    void push_R(T x) { R.push(x - add_R); }
    T pushpop_L(T x) {
        T L_max = top_L();
        if (x >= L_max) return x;
        L.pop();
        push_L(x);
        return L_max;
    }
    T pushpop_R(T x) {
        T R_min = top_R();
        if (x <= R_min) return x;
        R.pop();
        push_R(x);
        return R_min;
    }

    // f(x) += c
    void add_constant(T c) { min_f += c; }
    // f(x) += max(x - a, 0)
    void add_right_slope(T a) {
        min_f += std::max<T>(top_L() - a, 0);
        push_R(pushpop_L(a));
    }
    // f(x) += max(a - x, 0)
    void add_left_slope(T a) {
        min_f += std::max<T>(a - top_R(), 0);
        push_L(pushpop_R(a));
    }
    void remove_right_slope(T a) {
      if (top_R() <= a) R.erase(a);
      else {
        min_f -= top_R() - a;
        L.erase(a);
        L.emplace(R.top());
        R.pop();
      }
    }
    void remove_left_slope(T a) {
      if (a <= top_L()) L.erase(a);
      else {
        min_f -= a - top_L();
        R.erase(a);
        R.emplace(L.top());
        L.pop();
      }
    }
    // f(x) += abs(x - a)
    void add_v(T a) { add_right_slope(a); add_left_slope(a); }

    void shift(T a, T b) { 
        assert(a <= b);
        add_L += a;
        add_R += b;
    }
    void shift(T a) { shift(a, a); }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, d;
  cin >> n >> k >> d;
  VI h(n);
  rep(i, n) cin >> h[i];
  ll ans = accumulate(all(h), 0LL);
  SlopeTrick st;
  rep(i, k - 1) st.add_left_slope(h[i]), st.add_right_slope(h[i] + d);
  rep(i, n - k + 1) {
    st.add_left_slope(h[i+k-1]), st.add_right_slope(h[i+k-1] + d);
    chmin(ans, st.min_f);
    // cout << st.min_f << endl;
    st.remove_left_slope(h[i]), st.remove_right_slope(h[i] + d);
  }
  cout << ans << '\n';
}
0