結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
|
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#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"; }