結果
| 問題 | 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 | 
ソースコード
#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';
}
            
            
            
        