結果

問題 No.3303 Heal Slimes 2
ユーザー t98slider
提出日時 2025-10-05 16:29:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,277 bytes
コンパイル時間 4,166 ms
コンパイル使用メモリ 266,644 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2025-10-05 16:29:31
合計ジャッジ時間 8,388 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
constexpr int INF = 1 << 29;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, k, d;
    cin >> n >> k >> d;
    vector<ll> a(n), c;
    for(auto &&v : a) cin >> v;
    c = a;
    sort(c.begin(), c.end());
    atcoder::fenwick_tree<ll> fw1(n), fw2(n);
    multiset<ll> L, M, R;
    auto add = [&](ll p, int v){
        int pos = lower_bound(c.begin(), c.end(), p) - c.begin();
        fw1.add(pos, v);
        fw2.add(pos, v * p);
    };
    auto update = [&](){
        if(!M.empty()){
            while(true){
                ll mn = *M.begin();
                ll mx = *M.rbegin();
                if(mx - mn > d){
                    if(L.size() < R.size()){
                        L.insert(mn);
                        M.erase(M.find(mn));
                        add(mn, 1);
                    }else{
                        R.insert(mx);
                        M.erase(M.find(mx));
                        add(mx, 1);
                    }
                }else{
                    break;
                }
            }
        }
        while(L.size() >= R.size() + 2){
            ll v = *L.rbegin();
            L.erase(L.find(v));
            add(v, -1);
            M.insert(v);
            while(true){
                ll mn = *M.begin();
                ll mx = *M.rbegin();
                if(mx - mn > d){
                    R.insert(mx);
                    M.erase(M.find(mx));
                    add(mx, 1);
                }else{
                    break;
                }
            }
        }
        while(R.size() >= L.size() + 2){
            ll v = *R.begin();
            R.erase(R.find(v));
            add(v, -1);
            M.insert(v);
            while(true){
                ll mn = *M.begin();
                ll mx = *M.rbegin();
                if(mx - mn > d){
                    L.insert(mn);
                    M.erase(M.find(mn));
                    add(mn, 1);
                }else{
                    break;
                }
            }
        }
    };
    ll ans = 1ll << 60;
    for(int i = 0; i < n; i++){
        M.insert(a[i]);
        if(i >= k){
            if(L.find(a[i - k]) != L.end()){
                L.erase(L.find(a[i - k]));
                add(a[i - k], -1);
            }else if(M.find(a[i - k]) != M.end()){
                M.erase(M.find(a[i - k]));
            }else{
                R.erase(R.find(a[i - k]));
                add(a[i - k], -1);
            }
        }
        update();
        if(i >= k - 1){
            ll mn = *M.begin();
            ll mx = max(*M.rbegin(), mn + d);
            int lp = lower_bound(c.begin(), c.end(), mn) - c.begin();
            int rp = lower_bound(c.begin(), c.end(), mx) - c.begin();
            ans = min(ans, mn * fw1.sum(0, lp) - fw2.sum(0, lp) + fw2.sum(rp, n) - fw1.sum(rp, n) * mx);
            mx = *M.rbegin();
            mn = mx - d;
            lp = lower_bound(c.begin(), c.end(), mn) - c.begin();
            rp = lower_bound(c.begin(), c.end(), mx) - c.begin();
            ans = min(ans, mn * fw1.sum(0, lp) - fw2.sum(0, lp) + fw2.sum(rp, n) - fw1.sum(rp, n) * mx);
        
        }
    }
    cout << ans << '\n';
}
0