結果

問題 No.972 選び方のスコア
ユーザー はまやんはまやんはまやんはまやん
提出日時 2020-01-17 22:30:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,416 bytes
コンパイル時間 2,468 ms
コンパイル使用メモリ 214,524 KB
実行使用メモリ 8,568 KB
最終ジャッジ日時 2024-06-25 21:59:28
合計ジャッジ時間 7,477 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 164 ms
8,568 KB
testcase_01 AC 165 ms
8,560 KB
testcase_02 AC 156 ms
8,272 KB
testcase_03 AC 81 ms
6,940 KB
testcase_04 AC 165 ms
8,436 KB
testcase_05 AC 163 ms
8,560 KB
testcase_06 AC 162 ms
8,440 KB
testcase_07 AC 125 ms
7,476 KB
testcase_08 AC 149 ms
8,440 KB
testcase_09 AC 147 ms
8,284 KB
testcase_10 AC 103 ms
8,560 KB
testcase_11 AC 104 ms
8,432 KB
testcase_12 AC 108 ms
8,564 KB
testcase_13 AC 109 ms
8,352 KB
testcase_14 AC 109 ms
8,564 KB
testcase_15 AC 127 ms
8,436 KB
testcase_16 AC 124 ms
8,440 KB
testcase_17 AC 120 ms
8,436 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 2 ms
6,944 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 1 ms
6,940 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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