結果

問題 No.1391 ±1 Abs Sum
ユーザー m_tsubasam_tsubasa
提出日時 2021-02-12 22:13:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 3,415 bytes
コンパイル時間 2,363 ms
コンパイル使用メモリ 203,088 KB
最終ジャッジ日時 2025-01-18 18:43:37
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
  SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while (n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while (k >>= 1) dat[k] = f(dat[k << 1], dat[(k << 1) | 1]);
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
  // require: func(unit) == false
  // min left: st <= res && func(seg.query(st,res + 1))
  template <typename C>
  int find_left(int st, C &func, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(acc, dat[k]);
      return func(acc) ? l : -1;
    }
    int mid = (l + r) >> 1;
    if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);
    if (st <= l && !func(f(acc, dat[k]))) {
      acc = f(acc, dat[k]);
      return -1;
    }
    int nres = find_left(st, func, acc, (k << 1), l, mid);
    if (~nres) return nres;
    return find_left(st, func, acc, (k << 1) | 1, mid, r);
  }
  template <typename C>
  int find_left(int st, C &func) {
    T acc = unit;
    return find_left(st, func, acc, 1, 0, n);
  }

  // max right: res <= st && func(seg.query(res - 1,st))
  template <typename C>
  int find_right(int st, C &func, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = f(dat[k], acc);
      return func(acc) ? r : -1;
    }
    int mid = (l + r) >> 1;
    if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);
    if (r <= st && !func(f(dat[k], acc))) {
      acc = f(dat[k], acc);
      return -1;
    }
    int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);
    if (~nres) return nres;
    return find_right(st, func, acc, k << 1, l, mid);
  }
  template <typename C>
  int find_right(int st, C &func) {
    T acc = unit;
    return find_right(st, func, acc, 1, 0, n);
  }
};

int n, k;
vector<long long> a;
SegmentTree<long long> seg;

long long solve();

int main() {
  cin >> n >> k;
  a.resize(n);
  for (auto &p : a) cin >> p;
  cout << solve() << endl;
  return 0;
}
long long solve() {
  long long res = 1e17;
  {
    auto f = [](long long l, long long r) { return l + r; };
    seg = SegmentTree<long long>(a, f, 0);
  }
  k = n - k;
  for (int i = 0, id = 0; i < n; ++i) {
    auto calc = [&](int l, int r) {
      long long nres = 0;
      int nl = max(0, l), nr = min(r, i + 1);
      if (nl < nr) nres += a[i] * (nr - nl) - seg.query(nl, nr);
      nl = max(i + 1, l), nr = min(r, n);
      if (nl < nr) nres += seg.query(nl, nr) - a[i] * (nr - nl);
      return nres;
    };
    long long now = calc(0, n);
    while (id < k && abs(a[id] - a[i]) > abs(a[n - k + id] - a[i])) ++id;
    now -= 2 * (calc(0, id) + calc(n - k + id, n));
    res = min(res, now);
  }
  return res;
}
0