結果

問題 No.972 選び方のスコア
ユーザー lam6er
提出日時 2025-03-26 15:53:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,401 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 117,308 KB
最終ジャッジ日時 2025-03-26 15:54:07
合計ジャッジ時間 7,251 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
a = list(map(int, input().split()))
a.sort()
prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i+1] = prefix_sum[i] + a[i]

max_S = 0

for i in range(n):
    s_max = min(i, n - 1 - i)
    if s_max < 0:
        continue
    left_start = i - s_max
    left_sum = prefix_sum[i] - prefix_sum[left_start]
    sum_left_diff = a[i] * s_max - left_sum
    
    right_start = n - s_max
    right_sum = prefix_sum[n] - prefix_sum[right_start]
    sum_right_diff = right_sum - a[i] * s_max
    
    S = sum_right_diff - sum_left_diff
    if S > max_S:
        max_S = S

# Check for even cases (k even)
for s in range(1, n//2 + 1):
    # Check possible even k = 2s
    # median is (x_{s} + x_{s+1}) / 2
    # The best for even k would be to take the largest 2s elements?
    # Or find the best pair of middle elements.
    # This part is complex, but let's consider taking pairs of middle elements.
    for i in range(s-1, n - s):
        # The median is (a[i] + a[i+1])/2
        # take i - (s-1) to i + s
        # elements from i - (s-1) to i+s (total 2s elements)
        start = i - (s-1)
        end = i + s
        if start < 0 or end >= n:
            continue
        total = prefix_sum[end+1] - prefix_sum[start]
        median_val = (a[i] + a[i+1]) / 2
        S = total - 2 * s * median_val
        if S > max_S and S.is_integer():
            max_S = int(S)

print(max_S)
0