結果

問題 No.837 Noelちゃんと星々2
コンテスト
ユーザー Arumakan1727
提出日時 2019-06-14 22:15:28
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,571 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,841 ms
コンパイル使用メモリ 169,936 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-14 06:28:23
合計ジャッジ時間 3,517 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "bits/stdc++.h"
// Custom Header <<<
#define ALL(x) x.begin(), x.end()
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
#ifndef YDK
#define eprintf(...)
#endif
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD  = int(1e9) + 7;
// >>>


i64 slv(const int *a, const int *end)
{
    const int N = end - a;

    i64 sum = 0;
    if (N & 1) {
        const int med = a[N / 2];
        rep(i, 0, N) {
            sum += abs(med - a[i]);
        }
    } else {
        sum = LINF;
        for (int med : {a[N/2], a[N/2-1]}) {
            i64 tmp = 0;
            rep(i, 0, N) {
                tmp += abs(med - a[i]);
            }
            chmin(sum, tmp);
        }
    }

    return sum;

}

signed main()
{
    int N;
    int a[100010];
    cin >> N >> a[0];

    rep(i, 1, N) cin >> a[i];

    sort(a, a+N);

    if (a[0] == a[N-1]) {
        cout << 1 << endl;
        return 0;
    }

    const int mid = N / 2;

    i64 ans = LINF;
    rep(i, max(0, mid - 2), min(N, mid + 3)) {
        // rep(i, 0, mid) { cout << a[i] << ' '; } cout << endl;
        // rep(i, mid, N) { cout << a[i] << ' '; } cout << endl;
        chmin(ans, slv(a, a+i) + slv(a+i, a+N));
    }

    cout << ans << endl;
    return 0;
}

/* vim:set foldmethod=marker foldmarker=<<<,>>> : */
0