結果

問題 No.972 選び方のスコア
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:08:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,111 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 125,400 KB
最終ジャッジ日時 2025-06-12 16:08:11
合計ジャッジ時間 5,057 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    a = list(map(int, data[1:N+1]))
    a.sort()
    
    # Compute prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i+1] = prefix[i] + a[i]
    
    # Compute suffix sums
    suffix = [0] * (N + 1)
    for i in range(1, N+1):
        suffix[i] = suffix[i-1] + a[N - i]
    
    max_S = -float('inf')
    
    for k in range(1, N+1):
        if k % 2 == 1:
            # Odd
            m = (k - 1) // 2
            t = k - (m + 1)
            if t < 0:
                t = 0
            sum_subset = prefix[m+1] + suffix[t]
            median = a[m]
        else:
            # Even
            m = (k // 2) - 1
            t = k - (m + 1)
            if t < 0:
                t = 0
            sum_subset = prefix[m+1] + suffix[t]
            # The median is (a[m] + a[n - t]) / 2
            median = (a[m] + a[N - t]) / 2
        
        S = sum_subset - k * median
        if S > max_S:
            max_S = S
    
    print(int(max_S))

if __name__ == '__main__':
    main()
0