結果
問題 | No.837 Noelちゃんと星々2 |
ユーザー |
![]() |
提出日時 | 2020-03-05 18:52:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 1,409 bytes |
コンパイル時間 | 736 ms |
コンパイル使用メモリ | 49,720 KB |
最終ジャッジ日時 | 2025-01-09 04:34:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 void input(int& v)noexcept {v = 0; char c = gc();bool f = false;if (c == '-') { f = true; c = gc(); }for (; isdigit(c); c = gc()) {v *= 10;v += c - '0';}if (f)v = -v;}inline void input_l(long long& v)noexcept {v = 0; char c = gc();bool f = false;if (c == '-') {f = true; c = gc();}for (; isdigit(c); c = gc()) {v *= 10;v += c - '0';}if (f)v = -v;}int n;long long a[100001], s[100002];int main() {input(n);rep(i, n)input_l(a[i]);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);if (val >= ans)break;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);}