結果

問題 No.1391 ±1 Abs Sum
ユーザー m_tsubasam_tsubasa
提出日時 2021-02-12 22:13:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 3,415 bytes
コンパイル時間 2,252 ms
コンパイル使用メモリ 209,020 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-07-19 22:18:48
合計ジャッジ時間 6,097 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 134 ms
8,960 KB
testcase_12 AC 100 ms
8,448 KB
testcase_13 AC 123 ms
8,688 KB
testcase_14 AC 85 ms
6,272 KB
testcase_15 AC 92 ms
6,272 KB
testcase_16 AC 116 ms
8,448 KB
testcase_17 AC 98 ms
8,320 KB
testcase_18 AC 136 ms
8,704 KB
testcase_19 AC 86 ms
8,320 KB
testcase_20 AC 130 ms
8,912 KB
testcase_21 AC 84 ms
8,576 KB
testcase_22 AC 86 ms
8,492 KB
testcase_23 AC 98 ms
8,704 KB
testcase_24 AC 92 ms
8,616 KB
testcase_25 AC 91 ms
8,800 KB
testcase_26 AC 95 ms
8,704 KB
testcase_27 AC 65 ms
6,400 KB
testcase_28 AC 66 ms
6,528 KB
testcase_29 AC 89 ms
8,576 KB
testcase_30 AC 73 ms
8,440 KB
testcase_31 AC 132 ms
8,960 KB
testcase_32 AC 79 ms
6,144 KB
testcase_33 AC 91 ms
6,272 KB
testcase_34 AC 110 ms
8,740 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 120 ms
8,960 KB
権限があれば一括ダウンロードができます

ソースコード

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