結果

問題 No.3303 Heal Slimes 2
ユーザー tnakao0123
提出日時 2025-10-07 09:52:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,793 ms / 4,000 ms
コード長 2,393 bytes
コンパイル時間 849 ms
コンパイル使用メモリ 65,944 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-07 09:52:52
合計ジャッジ時間 25,534 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:78:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |   scanf("%d%d%d", &n, &k, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:79:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |   for (int i = 0; i < n; i++) scanf("%d", hs + i);
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3303.cc:  No.3303 Heal Slimes 2 - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 100000;
const long long LINF = 1LL << 62;

/* typedef */

using ll = long long;

template <typename T>
struct BIT {
  int n;
  vector<T> bits;
  
  BIT() {}
  BIT(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    bits.assign(n + 1, 0);
  }

  T sum(int x) {
    x = min(x, n);
    T s = 0;
    while (x > 0) {
      s += bits[x];
      x -= (x & -x);
    }
    return s;
  }

  void add(int x, T v) {
    if (x <= 0) return;
    while (x <= n) {
      bits[x] += v;
      x += (x & -x);
    }
  }
};

/* global variables */

int hs[MAX_N], uhs[MAX_N];
BIT<int> bit0;
BIT<ll> bit1;

/* subroutines */

ll calc(int n, int m, int d, int x) {
  int i = lower_bound(uhs, uhs + m, x) - uhs;
  int j = upper_bound(uhs, uhs + m, x + d) - uhs;
  int ci = bit0.sum(i);
  int cj = bit0.sum(m) - bit0.sum(j);
  ll si = bit1.sum(i);
  ll sj = bit1.sum(m) - bit1.sum(j);
  ll s = ((ll)x * ci - si) + (sj - (ll)(x + d) * cj);

  //printf(" calc(%d,%d,%d,%d) = %lld\n", n, m, d, x, s);
  return s;
}

/* main */

int main() {
  int n, k, d;
  scanf("%d%d%d", &n, &k, &d);
  for (int i = 0; i < n; i++) scanf("%d", hs + i);

  copy(hs, hs + n, uhs);
  sort(uhs, uhs + n);
  int m = unique(uhs, uhs + n) - uhs;
  int minh = uhs[0], maxh = uhs[m - 1];

  if (maxh - minh <= d) { puts("0"); return 0; }

  for (int i = 0; i < n; i++)
    hs[i] = lower_bound(uhs, uhs + m, hs[i]) - uhs;

  bit0.init(m); bit1.init(m);

  ll mins = LINF;
  for (int i = 0, j = 0; j < n; i++) {
    while (j < i + k) {
      bit0.add(hs[j] + 1, 1);
      bit1.add(hs[j] + 1, uhs[hs[j]]);
      j++;
    }

    int x0 = minh, x1 = maxh - d;
    while (x0 + 2 < x1) {
      int xx0 = ((ll)x0 * 2 + x1) / 3;
      int xx1 = ((ll)x0 + x1 * 2) / 3;
      ll c0 = calc(n, m, d, xx0);
      ll c1 = calc(n, m, d, xx1);
      if (c0 > c1) x0 = xx0;
      else x1 = xx1;
    }

    ll minc = LINF;
    int minx = -1;
    for (int x = x0; x <= x1; x++) {
      ll c = calc(n, m, d, x);
      if (minc > c) minc = c, minx = x;
    }
    mins = min(mins, minc);
    //printf(" %d,%d: minc=%lld, minx=%d\n", i, j, minc, minx);

    bit0.add(hs[i] + 1, -1);
    bit1.add(hs[i] + 1, -uhs[hs[i]]);
  }

  printf("%lld\n", mins);
  
  return 0;
}
0