結果

問題 No.972 選び方のスコア
コンテスト
ユーザー はまやんはまやん
提出日時 2020-01-17 22:30:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,416 bytes
コンパイル時間 2,529 ms
コンパイル使用メモリ 208,884 KB
最終ジャッジ日時 2025-01-08 18:58:16
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> struct MedianStructure {
	min_priority_queue<T> bigger; T sm_bigger = 0;
	priority_queue<T> smaller; T sm_smaller = 0;
	T center;
	int cnt = 0;
 
	void add(T v) {
		if (cnt == 0) center = v;
		else if (cnt == 1) {
			bigger.push(max(center, v)); sm_bigger += max(center, v);
			smaller.push(min(center, v)); sm_smaller += min(center, v);
		}else if (cnt % 2 == 0) {
			vector<T> vec; T a;
			a = bigger.top(); vec.push_back(a); bigger.pop(); sm_bigger -= a;
			a = smaller.top(); vec.push_back(a); smaller.pop(); sm_smaller -= a;
			vec.push_back(v);
			sort(all(vec));
			smaller.push(vec[0]); sm_smaller += vec[0];
			center = vec[1];
			bigger.push(vec[2]); sm_bigger += vec[2];
		}
		else {
			vector<T> vec; T a;
			a = bigger.top(); vec.push_back(a); bigger.pop(); sm_bigger -= a;
			a = smaller.top(); vec.push_back(a); smaller.pop(); sm_smaller -= a;
			vec.push_back(v);
			vec.push_back(center);
			sort(all(vec));
			smaller.push(vec[0]); sm_smaller += vec[0];
			smaller.push(vec[1]); sm_smaller += vec[1];
			bigger.push(vec[2]); sm_bigger += vec[2];
			bigger.push(vec[3]); sm_bigger += vec[3];
		}
 
		cnt++;
	}
	T getMedianGetSmall() {
		if (cnt % 2 == 0) return smaller.top();
		else return center;
	}
	T getMedian() {
		if (cnt % 2 == 0) return (smaller.top() + bigger.top()) / 2;
		else return center;
	}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];

	rep(i, 0, N) A[i] *= 2;
	sort(A, A + N);

	ll ans = -infl;
	rep(_, 0, 2) {
		vector<ll> v;
		rep(i, 0, N / 2) {
			v.push_back(A[i]);
			v.push_back(A[N - 1 - i]);
		}
		if (N % 2 == 1) v.push_back(A[N / 2]);

		ll tot = 0;
		MedianStructure<ll> ms;
		rep(i, 0, N) {
			ll k = i + 1;
			tot += v[i];
			ms.add(v[i]);

			ll S = tot - ms.getMedian() * k;
			chmax(ans, S);
		}

		reverse(all(v));
	}

	ans /= 2;
	cout << ans << endl;
}
0