結果
問題 | No.1391 ±1 Abs Sum |
ユーザー | define |
提出日時 | 2021-02-12 23:03:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 609 ms / 2,000 ms |
コード長 | 2,301 bytes |
コンパイル時間 | 2,860 ms |
コンパイル使用メモリ | 192,356 KB |
最終ジャッジ日時 | 2025-01-18 19:36:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 555 ms
6,912 KB |
testcase_12 | AC | 401 ms
6,144 KB |
testcase_13 | AC | 512 ms
6,400 KB |
testcase_14 | AC | 357 ms
5,248 KB |
testcase_15 | AC | 363 ms
5,632 KB |
testcase_16 | AC | 474 ms
5,888 KB |
testcase_17 | AC | 423 ms
5,632 KB |
testcase_18 | AC | 568 ms
6,272 KB |
testcase_19 | AC | 336 ms
5,632 KB |
testcase_20 | AC | 550 ms
6,528 KB |
testcase_21 | AC | 362 ms
6,016 KB |
testcase_22 | AC | 370 ms
6,144 KB |
testcase_23 | AC | 418 ms
6,528 KB |
testcase_24 | AC | 401 ms
6,144 KB |
testcase_25 | AC | 412 ms
6,400 KB |
testcase_26 | AC | 407 ms
6,656 KB |
testcase_27 | AC | 268 ms
5,632 KB |
testcase_28 | AC | 286 ms
5,632 KB |
testcase_29 | AC | 387 ms
6,272 KB |
testcase_30 | AC | 329 ms
5,888 KB |
testcase_31 | AC | 609 ms
6,784 KB |
testcase_32 | AC | 319 ms
5,376 KB |
testcase_33 | AC | 378 ms
5,504 KB |
testcase_34 | AC | 414 ms
6,528 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 353 ms
6,784 KB |
ソースコード
#line 2 "/home/defineprogram/Desktop/Library/template/template.cpp"#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i, n) for (int i = 0; i < n; i++)#define REP(i, n) for (int i = 1; i < n; i++)#define rev(i, n) for (int i = n - 1; i >= 0; i--)#define REV(i, n) for (int i = n - 1; i > 0; i--)#define all(v) v.begin(), v.end()#define PL pair<ll, ll>#define PI pair<int,int>#define len(s) (int)s.size()template <class T, class U>inline bool chmin(T &a, U b) {if (a > b) {a = b;return true;}return false;}template <class T, class U>inline bool chmax(T &a, U b) {if (a < b) {a = b;return true;}return false;}constexpr ll inf = 3e18;#line 3 "/home/defineprogram/Desktop/Library/structure/UnionFind.cpp"class UnionFind {int N;vector<int> par, siz;public:int find(int x) {assert(x < N);return (par[x] == x ? x : par[x] = find(par[x]));}void merge(int x, int y) {assert(x < N && y < N);x = find(x);y = find(y);if (x == y) return;if (siz[x] > siz[y]) swap(x, y);par[x] = y;siz[y] += siz[x];}bool same(int x, int y) {return find(x) == find(y);}int size(int x) {return siz[find(x)];}UnionFind(int N) : N(N), siz(N, 1), par(N) {iota(all(par), 0);}};/*@brief Union Find@docs docs/UnionFind.md*/#line 3 "main.cpp"int N,K;ll A[1<<18],sum[1<<18];int main() {cin.tie(0); ios::sync_with_stdio(false);cin>>N>>K;rep(i,N)cin>>A[i];rep(i,N){sum[i+1]=sum[i]+A[i];}ll ans=inf;rep(i,N){ll ok=2e9,ng=-1;while(ok-ng>1){ll mid=(ok+ng)/2;int l=lower_bound(A,A+N,A[i]-mid)-A;int r=upper_bound(A,A+N,A[i]+mid)-A;if(r-l>=K)ok=mid;else ng=mid;}int l=lower_bound(A,A+N,A[i]-ok)-A;int r=l+K;if(r<=i&&K){l+=(i-r+1);r+=(i-r+1);}ll memo=A[i]*(i-l)-(sum[i]-sum[l]);memo-=A[i]*l-sum[l];memo+=(sum[r]-sum[i])-A[i]*(r-i);memo-=(sum[N]-sum[r])-(N-r)*A[i];chmin(ans,memo);}cout<<ans<<"\n";}