/* #region Head */ #include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pll = pair; template using vc = vector; template using vvc = vc>; using vll = vc; using vvll = vvc; using vld = vc; using vvld = vvc; using vs = vc; using vvs = vvc; template using um = unordered_map; template using pq = priority_queue; template using pqa = priority_queue, greater>; template using us = unordered_set; #define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i)) #define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i)) #define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i)) #define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d)) #define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d)) #define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) #define ALL(x) begin(x), end(x) #define SIZE(x) ((ll)(x).size()) #define PERM(c) \ sort(ALL(c)); \ for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c))) #define UNIQ(v) v.erase(unique(ALL(v)), v.end()); #define CEIL(a, b) (((a) + (b)-1) / (b)) #define endl '\n' #define sqrt sqrtl #define floor floorl #define log2 log2l constexpr ll INF = 1'010'000'000'000'000'017LL; constexpr int IINF = 1'000'000'007LL; constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7 // constexpr ll MOD = 998244353; constexpr ld EPS = 1e-12; constexpr ld PI = 3.14159265358979323846; template istream &operator>>(istream &is, vc &vec) { // vector 入力 for (T &x : vec) is >> x; return is; } template ostream &operator<<(ostream &os, vc &vec) { // vector 出力 (for dump) os << "{"; REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", "); os << "}"; return os; } template ostream &operator>>(ostream &os, vc &vec) { // vector 出力 (inline) REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " "); return os; } template istream &operator>>(istream &is, pair &pair_var) { // pair 入力 is >> pair_var.first >> pair_var.second; return is; } template ostream &operator<<(ostream &os, pair &pair_var) { // pair 出力 os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // map, um, set, us 出力 template ostream &out_iter(ostream &os, T &map_var) { os << "{"; REPI(itr, map_var) { os << *itr; auto itrcp = itr; if (++itrcp != map_var.end()) os << ", "; } return os << "}"; } template ostream &operator<<(ostream &os, map &map_var) { return out_iter(os, map_var); } template ostream &operator<<(ostream &os, um &map_var) { os << "{"; REPI(itr, map_var) { auto [key, value] = *itr; os << "(" << key << ", " << value << ")"; auto itrcp = itr; if (++itrcp != map_var.end()) os << ", "; } os << "}"; return os; } template ostream &operator<<(ostream &os, set &set_var) { return out_iter(os, set_var); } template ostream &operator<<(ostream &os, us &set_var) { return out_iter(os, set_var); } template ostream &operator<<(ostream &os, pq &pq_var) { pq pq_cp(pq_var); os << "{"; if (!pq_cp.empty()) { os << pq_cp.top(), pq_cp.pop(); while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop(); } return os << "}"; } void pprint() { cout << endl; } template void pprint(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail) > 0) cout << ' '; pprint(move(tail)...); } // dump #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) DUMPOUT << ", "; dump_func(move(tail)...); } // chmax (更新「される」かもしれない値が前) template > bool chmax(T &xmax, const U &x, Comp comp = {}) { if (comp(xmax, x)) { xmax = x; return true; } return false; } // chmin (更新「される」かもしれない値が前) template > bool chmin(T &xmin, const U &x, Comp comp = {}) { if (comp(x, xmin)) { xmin = x; return true; } return false; } // ローカル用 #ifndef ONLINE_JUDGE #define DEBUG_ #endif #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif #define VAR(type, ...) \ type __VA_ARGS__; \ cin >> __VA_ARGS__; template istream &operator,(istream &is, T &rhs) { return is >> rhs; } template ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; } struct AtCoderInitialize { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; AtCoderInitialize() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cout << fixed << setprecision(IOS_PREC); if (AUTOFLUSH) cout << unitbuf; } } ATCODER_INITIALIZE; void Yn(bool p) { cout << (p ? "Yes" : "No") << endl; } void YN(bool p) { cout << (p ? "YES" : "NO") << endl; } /* #endregion */ // #include // using namespace atcoder; /* #region RBST */ // https://ei1333.github.io/luzhiled/snippets/structure/rbst.html // モノイド T と作用素 E template struct RandomizedBinarySearchTree { using F = function; using G = function; using H = function; using P = function; // 乱数生成 (xorshift) inline static uint32_t xor128() { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } // 木のノード struct Node { Node *l = nullptr, *r = nullptr; size_t cnt = 1ul; bool rev = false; T key, sum; E lazy; Node() = default; // 値 k を持つノードをつくる.作用素は p で初期化する. Node(const T &k, const E &p) : key(k), sum(k), lazy(p) {} }; using NodePair = pair; Node *root = nullptr; // 根 const T ti; // 要素の単位元,1 など. const E ei; // 作用素の単位元,0 など. const F f; // 要素と要素をマージする関数 const G g; // 要素に作用素を作用させる関数 const H h; // 作用素と作用素をマージする関数 const P p; // 要素に作用素を作用させる前に,区間の長さを考慮して作用素を加工して返す関数. // (作用素, 区間長さ) ->加工済み作用素. /** * コンストラクタ.遅延伝播・区間アップデートを行わない場合はこちら. * @param sz ノード数 * @param f 要素と要素をマージする関数 * @param ti 要素の単位元 */ RandomizedBinarySearchTree(const F &f, const T &ti) : ti(ti), ei(E()), f(f), g(G()), h(H()), p(P()) {} /** * コンストラクタ. * @param f 要素と要素をマージする関数 * @param g 要素に作用素を作用させる関数 * @param h 作用素と作用素をマージする関数 * @param p 要素に作用素を作用させる前に,区間の長さを考慮して作用素を加工して返す関数. * (作用素, 区間長さ) -> 加工済み作用素. * @param ti 要素の単位元 * @param ei 作用素の単位元 */ RandomizedBinarySearchTree(const F &f, const G &g, const H &h, const P &p, const T &ti, const E &ei) : ti(ti), ei(ei), f(f), g(g), h(h), p(p) {} // デストラクタ ~RandomizedBinarySearchTree() { sweep(root); } private: // 新しいノードを生成する inline Node *alloc(const T &key) { return new Node(key, ei); } virtual Node *clone(Node *t) { return t; } inline T sum(const Node *t) const { return t ? t->sum : ti; } // 子ノード再計算済み状態で,指定ノードの値を再計算する inline Node *recalc(Node *t) { t->cnt = count(t->l) + count(t->r) + 1ul; t->sum = f(f(sum(t->l), t->key), sum(t->r)); return t; } // 遅延を子ノードへ伝播する Node *propagate(Node *t) { t = clone(t); if (t->lazy != ei) { t->key = g(t->key, p(t->lazy, 1)); if (t->l) { t->l = clone(t->l); t->l->lazy = h(t->l->lazy, t->lazy); t->l->sum = g(t->l->sum, p(t->lazy, count(t->l))); } if (t->r) { t->r = clone(t->r); t->r->lazy = h(t->r->lazy, t->lazy); t->r->sum = g(t->r->sum, p(t->lazy, count(t->r))); } t->lazy = ei; } if (t->rev) { swap(t->l, t->r); if (t->l) t->l->rev ^= 1; if (t->r) t->r->rev ^= 1; t->rev = false; } return recalc(t); } // 木 l と木 r を併合する Node *merge(Node *l, Node *r) { if (!l || !r) return l ? l : r; if (xor128() % (l->cnt + r->cnt) < l->cnt) { l = propagate(l); l->r = merge(l->r, r); return recalc(l); } else { r = propagate(r); r->l = merge(l, r->l); return recalc(r); } } // 木 t を [0,k) [k,n) で分割する NodePair split(Node *t, size_t k) { if (!t) return {t, t}; t = propagate(t); if (k <= count(t->l)) { NodePair s = split(t->l, k); t->l = s.second; return {s.first, recalc(t)}; } else { NodePair s = split(t->r, k - count(t->l) - 1); t->r = s.first; return {recalc(t), s.second}; } } Node *build(size_t l, size_t r, const vc &v) { if (l + 1 >= r) return alloc(v[l]); return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v)); } // 木 t を再帰的に辿って,通りがけ順に値を配列に詰めていく void _dump(Node *t, typename vc::iterator &it) { if (!t) return; t = propagate(t); _dump(t->l, it); *it = t->key; _dump(t->r, ++it); } // 木 t の各ノードを通りがけ順に格納したものを返す.O(n). vc _dump(Node *t) { vc v(count(t)); typename vc::iterator it = begin(v); _dump(t, it); return v; } // 木 t の位置 k にノード v を挿入する void insert(Node *&t, size_t k, const T &v) { NodePair x = split(t, k); t = merge(merge(x.first, alloc(v)), x.second); } // k (0-indexed) 番目の要素を返す T kth_element(Node *t, size_t k) const { assert(k < count(t)); if (k < count(t->l)) return kth_element(t->l, k); if (k == count(t->l)) return t->key; return kth_element(t->r, k - count(t->l) - 1); } // 木 t の位置 k のノードを削除する void erase(Node *&t, size_t k) { NodePair x = split(t, k); NodePair y = split(x.second, 1); delete y.first; t = merge(x.first, y.second); } // 木を再帰的に消していく void sweep(Node *r) const { if (r == nullptr) return; if (r->l != nullptr) { sweep(r->l); r->l = nullptr; } if (r->r != nullptr) { sweep(r->r); r->r = nullptr; } delete r; } // 木 t の区間 [a, b) の値を二項演算した結果を返す T query(Node *&t, size_t a, size_t b) { // assert(b > a); if (a >= b) return ti; NodePair x = split(t, a); // 区間始点で左右に分割 NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割 T ret = sum(y.first); t = merge(x.first, merge(y.first, y.second)); return ret; } // 木 t の区間 [a, b) に作用素 p を適用する void update(Node *&t, size_t a, size_t b, const E &p) { // assert(b > a); if (a >= b) return; NodePair x = split(t, a); // 区間始点で左右に分割 NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割 y.first->lazy = h(y.first->lazy, p); t = merge(x.first, merge(propagate(y.first), y.second)); } // 木 t の区間 [a, b) を左右反転する void reverse(Node *&t, int a, int b) { assert(b > a); NodePair x = split(t, a); // 区間始点で左右に分割 NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割 if (y.first) y.first->rev ^= 1; t = merge(x.first, merge(y.first, y.second)); } // 木 t の区間 [a, b) に対して c 個ぶんの巡回シフト(右にズレる方向)をかける void circular_shift(Node *&t, int a, int b, int c) { assert(b > a); if (c == 0) return; if (c > 0) { // 右シフト c %= (b - a); if (c == 0) return; NodePair x = split(t, a); // 区間始点で左右に分割 NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割 NodePair z = split(y.first, b - a - c); // シフトで分割されるところで切る t = merge(x.first, merge(merge(z.second, z.first), y.second)); } else { // 左シフト c *= -1; c %= (b - a); if (c == 0) return; NodePair x = split(t, a); // 区間始点で左右に分割 NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割 NodePair z = split(y.first, c); // シフトで分割されるところで切る t = merge(x.first, merge(merge(z.second, z.first), y.second)); } } // 木 t の k (0-indexed) 番目の値を x に変更する void set_val(Node *&t, size_t k, const T &x) { t = propagate(t); if (k < count(t->l)) set_val(t->l, k, x); else if (k == count(t->l)) t->key = t->sum = x; else set_val(t->r, k - count(t->l) - 1, x); t = recalc(t); } // 木 t が空木かどうかを返す static bool empty(Node *t) { return !t; } protected: // 木 t のノード数を返す inline static size_t count(const Node *t) { return t ? t->cnt : 0ul; } public: // 木 root のノード数を返す size_t size() const { return count(root); } // ベクトル v をもとに木を構築する.O(n). void build(const vc &v) { // ptr = 0; root = build(0ul, v.size(), v); } // 木 root の位置 k にノード v を挿入する void insert(size_t k, const T &v) { NodePair x = split(root, k); root = merge(merge(x.first, alloc(v)), x.second); } // 木 root の k (0-indexed) 番目の要素を返す T kth_element(size_t k) const { return kth_element(this->root, k); } // 木 root の位置 k のノードを削除する void erase(size_t k) { NodePair x = split(root, k); NodePair y = split(x.second, 1); delete y.first; root = merge(x.first, y.second); } // 木 root の区間 [a, b) の値を二項演算した結果を返す T query(size_t a, size_t b) { return query(root, a, b); } // 木 root の区間 [a, b) に作用素 p を適用する void update(size_t a, size_t b, const E &p) { update(root, a, b, p); } // 木 root の区間 [a, b) を左右反転する void reverse(int a, int b) { reverse(root, a, b); } // 木 t の区間 [a, b) に対して c 個ぶんの巡回シフト(右にズレる方向)をかける void circular_shift(int a, int b, int c) { circular_shift(root, a, b, c); } // 木 root の k (0-indexed) 番目の値を x に変更する void set_val(size_t k, const T &x) { set_val(root, k, x); } // 木 root が空木かどうかを返す bool empty() { return empty(root); } // 木 root の各ノードを通りがけ順に格納したものを返す.O(n). vc _dump() { return _dump(root); } }; /* #endregion */ /* #region OrderedSet */ // k 番目が取れる多重集合(昇順ソート済みベクトルとして扱える) template struct OrderedMultiSet : RandomizedBinarySearchTree { using RBST = RandomizedBinarySearchTree; using Node = typename RBST::Node; using F = function; using G = function; using H = function; using P = function; // コンストラクタ OrderedMultiSet() : RBST([](T x, [[maybe_unused]] T y) -> T { return x; }, T()) {} // コンストラクタ OrderedMultiSet(const F &f, const G &g, const H &h, const P &p, const T &ti, const E &ei) : RBST(f, g, h, p, ti, ei) {} // 多重集合のサイズを返す size_t size() const { return RBST::size(); } // 多重集合に値 x を挿入する virtual void insert(const T &x) { RBST::insert(lower_bound(x), x); } // 多重集合から値 x を削除する void erase(const T &x) { if (!count(x)) return; RBST::erase(lower_bound(this->root, x)); } void erase_kth_element(const size_t k) { assert(k < size()); RBST::erase(k); } // 多重集合に含まれる値 x の個数を返す size_t count(const T &x) const { return count(this->root, x); } // x 以上の最小の要素のインデックスを返す size_t lower_bound(const T &x) const { return lower_bound(this->root, x); } // x より大きい最小の要素のインデックスを返す size_t upper_bound(const T &x) const { return upper_bound(this->root, x); } private: // 木 t に含まれる値 x の個数を返す size_t count(Node *t, const T &x) const { return upper_bound(t, x) - lower_bound(t, x); } // 木 t に含まれる x 以上の最小の要素のインデックスを返す size_t lower_bound(Node *t, const T &x) const { if (!t) return 0ul; if (x <= t->key) return lower_bound(t->l, x); return lower_bound(t->r, x) + RBST::count(t->l) + 1ul; } // 木 t に含まれる x より大きい最小の要素のインデックスを返す size_t upper_bound(Node *t, const T &x) const { if (!t) return 0ul; if (x < t->key) return upper_bound(t->l, x); return upper_bound(t->r, x) + RBST::count(t->l) + 1ul; } }; // 1 種類の値は1つのみ格納する通常の集合,k 番目が取れるようになったもの template struct OrderedSet : OrderedMultiSet { using SET = OrderedMultiSet; using RBST = typename SET::RBST; using Node = typename RBST::Node; OrderedSet() : OrderedMultiSet() {} // 集合に値 x を挿入する.既に値 x が存在する場合は何もしない. void insert(const T &x) override { if (SET::count(x)) return; RBST::insert(SET::lower_bound(x), x); } }; /* #endregion */ // Problem void solve() { VAR(ll, n, k); vll a(n); cin >> a; using F = function; using P = function; F f = [](ll a, ll b) -> ll { return a + b; }; // 要素のマージ P p = [](ll a, size_t b) -> ll { return a * b; }; OrderedMultiSet st(f, f, f, p, 0, 0); REP(i, 0, k - 1) st.insert(a[i]); ll mi = INF; REPM(r, k, n) { st.insert(a[r - 1]); ll l = r - k; ll m = (k - 1) / 2; ll median = st.kth_element((k - 1) / 2); ll sum_l = st.query(0, m); ll sum_r = st.query(m + 1, k); ll cost_l = median * (m - 0) - sum_l; ll cost_r = sum_r - median * (k - (m + 1)); ll cost = cost_l + cost_r; chmin(mi, cost); st.erase(a[l]); } pprint(mi); } // entry point int main() { solve(); return 0; }