結果
問題 |
No.3303 Heal Slimes 2
|
ユーザー |
![]() |
提出日時 | 2025-10-05 16:00:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 416 ms / 4,000 ms |
コード長 | 2,901 bytes |
コンパイル時間 | 1,026 ms |
コンパイル使用メモリ | 89,632 KB |
実行使用メモリ | 8,924 KB |
最終ジャッジ日時 | 2025-10-06 12:48:03 |
合計ジャッジ時間 | 7,667 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <tuple> #include <cstdio> #include <cassert> #include <atcoder/fenwicktree> #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; using namespace atcoder; int n, K, D; int h[100000]; vector<int> xs; //左端の候補 vector<int> hs; //ソートした高さ列(相異なる)。セグ木のi番目がhs[i]に対応 signed main() { int i; cin >> n >> K >> D; rep(i, n) cin >> h[i]; rep(i, n) { xs.push_back(h[i] - D); xs.push_back(h[i]); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); rep(i, n) hs.push_back(h[i]); sort(hs.begin(), hs.end()); hs.erase(unique(hs.begin(), hs.end()), hs.end()); fenwick_tree<int> fwCnt(hs.size()); fenwick_tree<int> fwSum(hs.size()); vector<int> hid(n); rep(i, n) { hid[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin(); if (i < K) { fwCnt.add(hid[i], 1); fwSum.add(hid[i], h[i]); } } int ans = 1e+18; rep(i, n - K + 1) { // cost(xs[ok]) <= cost(xs[ok + 1]) を満たす最小のokを求める int ng = -1, ok = xs.size(), mid; while (ok - ng >= 2) { mid = (ok + ng) / 2; //差分を求める int x = xs[mid]; int it1 = upper_bound(hs.begin(), hs.end(), x) - hs.begin(); int it2 = upper_bound(hs.begin(), hs.end(), x + D) - hs.begin(); int cnt1 = fwCnt.sum(0, it1); int cnt2 = fwCnt.sum(it2, hs.size()); //cout << "- x: " << x << ", cnt1: " << cnt1 << ", cnt2: " << cnt2 << endl; if (cnt1 >= cnt2) ok = mid; else ng = mid; } int x = xs[ok]; int it1 = upper_bound(hs.begin(), hs.end(), x) - hs.begin(); int it2 = upper_bound(hs.begin(), hs.end(), x + D) - hs.begin(); int cnt1 = fwCnt.sum(0, it1); int cnt2 = fwCnt.sum(it2, hs.size()); int ssum1 = fwSum.sum(0, it1); int ssum2 = fwSum.sum(it2, hs.size()); int cst1 = cnt1 * x - ssum1; int cst2 = ssum2 - cnt2 * (x + D); int cst = cst1 + cst2; //cout << "i: " << i << ", x: " << x << ", it1: " << it1 << ", it2: " << it2 << ", cnt1: " << cnt1 << ", cnt2: " << cnt2 << ", sum1: " << ssum1 << ", sum2: " << ssum2 << ", cst1: " << cst1 << ", cst2: " << cst2 << ", cst: " << cst << endl; ans = min(ans, cst); //h[i]の削除とh[i + K]の追加 fwCnt.add(hid[i], -1); fwSum.add(hid[i], -h[i]); if (i + K < n) { fwCnt.add(hid[i + K], 1); fwSum.add(hid[i + K], h[i + K]); } } cout << ans << endl; return 0; }