結果
問題 | No.837 Noelちゃんと星々2 |
ユーザー |
![]() |
提出日時 | 2020-03-05 18:47:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,410 bytes |
コンパイル時間 | 635 ms |
コンパイル使用メモリ | 49,980 KB |
最終ジャッジ日時 | 2025-01-09 04:33:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC target ("avx")#pragma GCC optimize ("Ofast")#include <cstdio>#include <cctype>#include <algorithm>using namespace std;#define rep(i, n) for (int i = 0; i < (n); ++i)#define FOR(i, m, n) for (int i = (m); i < (n); ++i)//#define LOCAL#ifdef LOCAL#define gc _getchar_nolock#include "dump.hpp"#else#define gc getchar_unlocked#define dump(...) ((void)0)#endifinline int input()noexcept {int v = 0; char c = gc();bool f = false;if (c == '-') {f = true; c = gc();}for (; isdigit(c); c = gc()) {v *= 10;v += c - '0';}return f ? -v : v;}inline long long input_l()noexcept {long long v = 0; char c = gc();bool f = false;if (c == '-') {f = true; c = gc();}for (; isdigit(c); c = gc()) {v *= 10;v += c - '0';}return f ? -v : v;}int n;long long a[100001], s[100002];int main() {n = input();rep(i, n)a[i] = input_l();sort(a, a + n);if (a[0] == a[n - 1]) {puts("1");return 0;}rep(i, n)s[i + 1] = s[i] + a[i];long long ans = 1e16;int l = -1, r = n / 2;if (!(n & 1))--r;FOR(i, 1, n) { // [0, i) + [i, n)if (i & 1)++l;if ((n - i) & 1)++r;long long val = 0;val += a[l] * l - s[l];val += (s[i] - s[l + 1]) - a[l] * (i - l - 1);val += a[r] * (r - i) - (s[r] - s[i]);val += (s[n] - s[r + 1]) - a[r] * (n - r - 1);if (ans > val)ans = val;}printf("%lld\n", ans);}