結果

問題 No.3303 Heal Slimes 2
ユーザー jupiter_68
提出日時 2025-10-05 14:52:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,144 bytes
コンパイル時間 1,839 ms
コンパイル使用メモリ 200,736 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 14:53:42
合計ジャッジ時間 4,240 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
class Point {
public:
    ld x;
    ld y;
    Point(ld _x = 0, ld _y = 0) : x(_x), y(_y) {}
    Point operator+(Point p) { return Point(x + p.x, y + p.y); }
    Point operator-(Point p) { return Point(x - p.x, y - p.y); }
    Point operator*(ld a) { return Point(a * x, a * y); }
    Point operator/(ld a) { return Point(x / a, y / a); }

    ld abs() { return sqrt(norm()); }
ld norm() { return x * x + y * y; }

    bool operator<(const Point& p) const {
        return !equals(x, p.x) ? x < p.x : y < p.y;
    }
    bool operator==(const Point& p) const {
        return fabs(x - p.x) < (1e-10) && fabs(y - p.y) < (1e-10);
    }
};
typedef Point Vector;
struct Segment {
    Point A;
    Point B;
};
typedef Segment Line;
class Circle {
public:
    Point C;
    ld r;
    Circle(Point C = Point(), ld r = 0.0) : C(C), r(r) {}
};
typedef vector<Point> Polygon;

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

void solve(){
    ll N, K, D; cin >> N >> K >> D;
    vl a(N); rep(i, N) cin >> a[i];
    ll L = -1, R = 1e9+1;
    auto f = [&](ll low, ll high)->ll{
        vl b(N);
        rep(i, N) b[i] = max({0LL, low - a[i], a[i] - high});
        ll re = 4e18;
        ll ct = 0;
        rep(i, K) ct += b[i];
        chmin(re, ct);
        reps(i, K, N){
            ct -= b[i-K];
            ct += b[i];
            chmin(re, ct);
        }
        return re;
    };
    while(R - L > 2){
        ll ml = (L+L+R)/3, mr = (L+R+R)/3;
        ll sl = f(ml, ml+D), sr = f(mr, mr+D);
        if(sl <= sr) R = mr;
        else L = ml;
    }
    ll ans = 4e18;
    reps(i, L, R+1){
        chmin(ans, f(i, i+D));
    }
    cout << ans << endl;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
0