結果

問題 No.2304 Distinct Elements
ユーザー 沙耶花沙耶花
提出日時 2023-05-12 22:30:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 126 ms / 3,000 ms
コード長 1,651 bytes
コンパイル時間 4,659 ms
コンパイル使用メモリ 267,556 KB
実行使用メモリ 6,492 KB
最終ジャッジ日時 2024-05-06 12:34:02
合計ジャッジ時間 9,605 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 66 ms
6,236 KB
testcase_05 AC 98 ms
6,364 KB
testcase_06 AC 70 ms
6,236 KB
testcase_07 AC 66 ms
6,236 KB
testcase_08 AC 88 ms
6,364 KB
testcase_09 AC 126 ms
6,236 KB
testcase_10 AC 125 ms
6,232 KB
testcase_11 AC 125 ms
6,236 KB
testcase_12 AC 124 ms
6,364 KB
testcase_13 AC 125 ms
6,240 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 79 ms
6,168 KB
testcase_30 AC 8 ms
5,376 KB
testcase_31 AC 65 ms
5,376 KB
testcase_32 AC 100 ms
6,200 KB
testcase_33 AC 9 ms
5,376 KB
testcase_34 AC 101 ms
6,080 KB
testcase_35 AC 112 ms
6,288 KB
testcase_36 AC 8 ms
5,376 KB
testcase_37 AC 24 ms
5,376 KB
testcase_38 AC 73 ms
6,352 KB
testcase_39 AC 74 ms
6,236 KB
testcase_40 AC 41 ms
6,232 KB
testcase_41 AC 22 ms
5,376 KB
testcase_42 AC 54 ms
6,360 KB
testcase_43 AC 112 ms
6,240 KB
testcase_44 AC 90 ms
6,012 KB
testcase_45 AC 64 ms
5,376 KB
testcase_46 AC 50 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 3 ms
5,376 KB
testcase_49 AC 83 ms
6,236 KB
testcase_50 AC 95 ms
6,240 KB
testcase_51 AC 94 ms
6,368 KB
testcase_52 AC 75 ms
6,236 KB
testcase_53 AC 77 ms
6,236 KB
testcase_54 AC 62 ms
6,240 KB
testcase_55 AC 59 ms
6,364 KB
testcase_56 AC 57 ms
6,364 KB
testcase_57 AC 87 ms
6,364 KB
testcase_58 AC 84 ms
6,232 KB
testcase_59 AC 63 ms
6,492 KB
testcase_60 AC 2 ms
5,376 KB
testcase_61 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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