結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0