結果

問題 No.972 選び方のスコア
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-06 23:48:15
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 38 ms / 2,000 ms
+ 417µs
コード長 3,225 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,884 ms
コンパイル使用メモリ 670,704 KB
実行使用メモリ 9,868 KB
最終ジャッジ日時 2026-11-06 23:48:33
合計ジャッジ時間 17,300 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

// import BinaryHeap;
// import BoolArray;
// import CPLib.Arithmetic;
// import CPLib.Bipartite;
// import CPLib.Bits;
// import CPLib.Convolution;
// import CPLib.DSegtree;
// import CPLib.Graph;
import CPLib.IO;
// import CPLib.LDSegtree;
// import CPLib.LSegtree;
// import CPLib.MaxFlow;
// import CPLib.Memoize;
// import CPLib.MinCostFlow;
// import CPLib.Misc;
// import CPLib.Monoid;
// import CPLib.Segtree;
// import CPLib.String;
// import CPLib.Trait;
// import CPLib.TwoSat;
// import CPLib.UnionFind;
// import CPLib.ZP;
// import HashMap;
// import HashSet;

main : IO () = (
    let iN = *read_i;
    let iAs = *read_is(iN);
    let iAs = iAs.sort;
    let acm = range(0, iN).fold([0], |i, acm| 
        let prev = acm.@(i);
        acm.push_back(iAs.@(i) + prev)
    );
    let ans0 = range(0, iN).map(|i|
        let n = min(i, iN-i-1);
        if n == 0 { 0 };
        let good = |m| (
            let j = iN - m;
            let k = i - m;
            iAs.@(j) + iAs.@(k) - 2 * iAs.@(i) > 0
        );
        let m = (
            if !good(1) {
                0
            };
            if good(n) {
                n
            };
            let lo = 0; let hi = n;
            loop((lo, hi), |(lo, hi)|
                if hi - lo <= 1 {
                    lo.break
                };
                let mid = lo + (hi - lo) / 2;
                if good(mid) {
                    let lo = mid;
                    (lo, hi).continue
                } else {
                    let hi = mid;
                    (lo, hi).continue
                }
            )
        );
        let sum = iAs.@(i) + acm.@(iN) - acm.@(iN - m) + acm.@(i) - acm.@(i-m);
        let score = sum - iAs.@(i) * (1 + 2 * m);
        // eval "score = {}, odd, i = {}, m = {}, sum = {}, iAs.@(i) = {}, medians = {}".debug_eprintfln((score, i, m, sum, iAs.@(i), iAs.@(i) * (1 + 2 * m)));
        score
    ).fold(I64::minimum, max);
    let ans1 = range(0, iN - 1).map(|i|
        let j = i + 1;
        let n = min(iN - j - 1, i);
        if n == 0 { 0 };
        let good = |m| (
            let k = i - m;
            let l = iN - m;
            iAs.@(k) + iAs.@(l) - (iAs.@(i) + iAs.@(j)) > 0
        );
        let m = (
            if !good(1) {
                0
            };
            if good(n) {
                n
            };
            let lo = 0; let hi = n;
            loop((lo, hi), |(lo, hi)|
                if hi - lo <= 1 {
                    lo.break
                };
                let mid = lo + (hi - lo) / 2;
                if good(mid) {
                    let lo = mid;
                    (lo, hi).continue
                } else {
                    let hi = mid;
                    (lo, hi).continue
                }
            )
        );
        let sum2 = iAs.@(i) + iAs.@(j) + acm.@(iN) - acm.@(iN - m) + acm.@(i) - acm.@(i - m);
        let score = sum2 - (iAs.@(i) + iAs.@(j)) * (1 + m);
        // eval "score = {}, even, i = {}, m = {}, sum2 = {}, mediums = {}".debug_eprintfln((score, i, m, sum2, (iAs.@(i) + iAs.@(j)) * (1 + m)));
        score
    ).fold(I64::minimum, max);
    let ans = ans0.max(ans1);
    ans.to_string.println;;
    pure()
);
0