#418705 (C++14) No.972 選び方のスコア

• 問題: No.972 選び方のスコア
• ユーザー: square1001
• 提出日時: 2020-01-17 22:02:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 166 ms / 2,000 ms
• コード長: 921 bytes
• コンパイル時間: 676 ms
• コンパイル使用メモリ: 75,680 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2024-06-25 20:07:18
• 合計ジャッジ時間: 5,301 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	130 ms; 6,528 KB
testcase_01	AC	132 ms; 6,272 KB
testcase_02	AC	123 ms; 6,144 KB
testcase_03	AC	57 ms; 5,376 KB
testcase_04	AC	117 ms; 6,400 KB
testcase_05	AC	119 ms; 6,400 KB
testcase_06	AC	118 ms; 6,400 KB
testcase_07	AC	94 ms; 5,632 KB
testcase_08	AC	110 ms; 6,400 KB
testcase_09	AC	107 ms; 6,400 KB
testcase_10	AC	110 ms; 6,528 KB
testcase_11	AC	113 ms; 6,400 KB
testcase_12	AC	111 ms; 6,400 KB
testcase_13	AC	113 ms; 6,400 KB
testcase_14	AC	114 ms; 6,400 KB
testcase_15	AC	115 ms; 6,400 KB
testcase_16	AC	117 ms; 6,400 KB
testcase_17	AC	166 ms; 6,400 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	111 ms; 6,528 KB
testcase_20	AC	113 ms; 6,400 KB
testcase_21	AC	114 ms; 6,400 KB
testcase_22	AC	111 ms; 6,400 KB
testcase_23	AC	109 ms; 6,272 KB
testcase_24	AC	110 ms; 6,272 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	2 ms; 5,376 KB
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	2 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB

ソースコード

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 62;
int main() {
	int N;
	cin >> N;
	vector<long long> A(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
	sort(A.begin(), A.end());
	vector<long long> S(N + 1);
	for (int i = 0; i < N; ++i) S[i + 1] = S[i] + A[i];
	long long ans = -inf;
	for (int i = 0; i < N; ++i) {
		int l = 0, r = min(i, N - i - 1) + 1;
		while (r - l > 1) {
			int m = (l + r) >> 1;
			if (A[N - m] + A[i - m] >= 2 * A[m]) l = m;
			else r = m;
		}
		ans = max(ans, S[N] - S[N - l] + S[i + 1] - S[i - l] - A[i] * (2 * l + 1));
	}
	for (int i = 0; i < N - 1; ++i) {
		int l = 0, r = min(i, N - i - 2) + 1;
		while (r - l > 1) {
			int m = (l + r) >> 1;
			if (A[N - m] + A[i - m] >= 2 * A[m]) l = m;
			else r = m;
		}
		ans = max(ans, S[N] - S[N - l] + S[i + 2] - S[i - l] - (A[i] + A[i + 1]) * (l + 1));
	}
	cout << ans << endl;
	return 0;
}