結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0