結果
問題 | No.2304 Distinct Elements |
ユーザー |
![]() |
提出日時 | 2023-05-12 22:30:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 133 ms / 3,000 ms |
コード長 | 1,651 bytes |
コンパイル時間 | 4,318 ms |
コンパイル使用メモリ | 258,460 KB |
最終ジャッジ日時 | 2025-02-12 23:14:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 58 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 struct slope_trick{ priority_queue<long long> L; priority_queue<long long,vector<long long>,greater<long long>> R; long long min_f=0; long long addL=0, addR=0; slope_trick(long long INF){ R.push(INF); L.push(-INF); } void add_constant(long long a){ min_f += a; } //+= max(0,x-a) void add_plus(long long a){ min_f += max(0LL, (L.top()+addL)-a); L.push(a-addL); R.push(L.top()+addL-addR); L.pop(); } //+= max(0,a-x) void add_minus(long long a){ min_f += max(0LL, a-(R.top()+addR)); R.push(a-addR); L.push(R.top()+addR-addL); R.pop(); } //[x-b, x-a] void slide(long long a,long long b){ if(a>b)swap(a,b); addL += a; addR += b; } long long get(long long x){ long long ret = min_f; priority_queue<long long> nL; priority_queue<long long,vector<long long>,greater<long long>> nR; while(L.size()>0){ ret += max(0LL, (L.top()+addL) - x); nL.push(L.top()+addL); L.pop(); } while(R.size()>0){ ret += max(0LL, x - (R.top()+addR)); nR.push(R.top()+addR); R.pop(); } swap(L,nL); swap(R,nR); addL = 0; addR = 0; return ret; } }; int main(){ int n; cin>>n; vector<int> a(n); rep(i,n)cin>>a[i]; sort(a.begin(),a.end()); rep(i,n)a[i] -= i; slope_trick S(Inf64); rep(i,n){ while(S.R.size()>0)S.R.pop(); S.add_plus(a[i]); S.add_minus(a[i]); } cout<<S.min_f<<endl; return 0; }