結果

問題 No.3303 Heal Slimes 2
ユーザー Magentor
提出日時 2025-10-05 14:48:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,104 bytes
コンパイル時間 5,563 ms
コンパイル使用メモリ 334,312 KB
実行使用メモリ 12,832 KB
最終ジャッジ日時 2025-10-05 14:48:43
合計ジャッジ時間 10,412 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)
typedef long long ll;
#define updiv(N,X) (N + X - 1) / X
#define l(n) n.begin(),n.end()
#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"
using P = pair<int, int>;
using mint = modint;
const int MOD = 998244353LL;
const ll INF = 999999999999LL;
vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
template <typename T>
void input(vector<T> &v){
 rep(i,v.size()){cin>>v[i];}
  return;
}
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll POW(ll a,ll n){
  long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

template< typename T, typename Compare = less< T >, typename RCompare = greater< T > >
struct PrioritySumStructure {

  size_t k;
  T sum;

  priority_queue< T, vector< T >, Compare > in, d_in;
  priority_queue< T, vector< T >, RCompare > out, d_out;

  PrioritySumStructure(int k) : k(k), sum(0) {}

  void modify() {
    while(in.size() - d_in.size() < k && !out.empty()) {
      auto p = out.top();
      out.pop();
      if(!d_out.empty() && p == d_out.top()) {
        d_out.pop();
      } else {
        sum += p;
        in.emplace(p);
      }
    }
    while(in.size() - d_in.size() > k) {
      auto p = in.top();
      in.pop();
      if(!d_in.empty() && p == d_in.top()) {
        d_in.pop();
      } else {
        sum -= p;
        out.emplace(p);
      }
    }
    while(!d_in.empty() && in.top() == d_in.top()) {
      in.pop();
      d_in.pop();
    }
  }

  T query() const {
    return sum;
  }

  void insert(T x) {
    in.emplace(x);
    sum += x;
    modify();
  }

  void erase(T x) {
    assert(size());
    if(!in.empty() && in.top() == x) {
      sum -= x;
      in.pop();
    } else if(!in.empty() && RCompare()(in.top(), x)) {
      sum -= x;
      d_in.emplace(x);
    } else {
      d_out.emplace(x);
    }
    modify();
  }

  void set_k(size_t kk) {
    k = kk;
    modify();
  }

  size_t get_k() const {
    return k;
  }

  size_t size() const {
    return in.size() + out.size() - d_in.size() - d_out.size();
  }
};

template< typename T >
using MaximumSum = PrioritySumStructure< T, greater< T >, less< T > >;

template< typename T >
using MinimumSum = PrioritySumStructure< T, less< T >, greater< T > >;

int main() {
  ll n,k,d;cin>>n>>k>>d;
  vector<ll> v(n);
  rep(i,n){cin>>v[i];}
  //minの位置を持つ関数
  //abs(h[i]-t)+abs(h[i]+d-t)-d
  /*multiset<ll> st1,st2;
  ll sm1 = 0;ll sm2 = 0;
  rep(i,d-1){
  	st1.insert(h[i]);sm1 += h[i];
  	st1.insert(h[i]+d);sm1 += h[i]+d;
  }
  rep(i,d-1){
  	ll y = *st1.rbegin();
  	st1.erase(st1.find(y));
  	sm1 -= y;sm2 += y;
  	st2.insert(y);
  }
  ll mn = 999999999999LL;
  rep(i,n-k+1){
  	//->add v[i+k-1]->del v[i]
  	ll nw = v[i+k-1];
  	st1.insert(nw);sm1 += nw;
  	st2.insert(nw+d);sm2 += nw+d;
  	while(true){
  		if(*st1.rbegin()<=*st2.begin()){break;}
  		ll aa = *st1.rbegin();sm1 -= aa;
  		ll bb = *st2.begin();sm2 -= bb;sm2 += aa;sm1 += bb;
  		st1.erase(st1.find(aa));
  		st2.erase(st2.find(bb));
  		st1.insert(bb);
  		st2.insert(aa);
  	}
  	mn = min(mn,(sm2-d*st1.rbegin())+(d*st1.rbegin()-sm1)-k*d);
  	
  	if(st1.count(v[i])){st1.erase(st1.find(v[i]));sm1 -= v[i];}
  	else{
  		st2.erase(st2.find(v[i]));sm2 -= v[i];
  	}
  	
  	
  	
  }*/
  MaximumSum<ll> sm1(k);
  MinimumSum<ll> sm2(k);
  rep(i,k-1){
    sm1.insert(v[i]);
    sm2.insert(v[i]);
    sm1.insert(v[i]-d);
    sm2.insert(v[i]-d);
  }
  ll mn = 99999999999999LL;
  rep(i,n-k+1){
    sm1.insert(v[i+k-1]);
    sm2.insert(v[i+k-1]);
    sm1.insert(v[i+k-1]-d);
    sm2.insert(v[i+k-1]-d);
    ll p = sm1.d_in.top();
    mn = min(mn,((sm1.query()-sm2.query())-k*d)/2);
    
    sm1.erase(v[i+k-1]);
    sm2.erase(v[i+k-1]);
    sm1.erase(v[i+k-1]-d);
    sm2.erase(v[i+k-1]-d);
    
  }
  cout << mn << endl;
}
0