結果

問題 No.1391 ±1 Abs Sum
ユーザー gew1fw
提出日時 2025-06-12 13:22:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,947 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 60,640 KB
最終ジャッジ日時 2025-06-12 13:24:47
合計ジャッジ時間 4,696 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    A.sort()
    
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + A[i]
    
    if K == 0:
        sum1 = 0
        for ai in A:
            sum1 += abs(A[0] - ai)
        sumN = 0
        for ai in A:
            sumN += abs(A[-1] - ai)
        max_sum = max(sum1, sumN)
        print(-max_sum)
        return
    
    min_val = float('inf')
    
    for j in range(N):
        current_A = A[j]
        sum_L = current_A * j - (prefix_sum[j] - prefix_sum[0])
        sum_R = (prefix_sum[N] - prefix_sum[j+1]) - current_A * (N - j - 1)
        sum_total = sum_L + sum_R
        
        t_low = max(0, (K-1) - (N-1 - j))
        t_high = min(K-1, j)
        t = t_low
        
        while t < t_high:
            next_t = t + 1
            next_s = K-1 - next_t
            if next_s < 0 or (j + next_s + 1) >= N:
                break
            if j - next_t < 0:
                break
            left_diff = current_A - A[j - next_t]
            right_diff = A[j + next_s + 1] - current_A
            if left_diff < right_diff:
                t = next_t
            else:
                break
        
        s = K-1 - t
        if t > j or s < 0 or (j + s + 1) > N:
            continue
        
        if j - t < 0:
            sum_left = 0
        else:
            sum_left = current_A * t - (prefix_sum[j] - prefix_sum[j - t])
        
        if j + s + 1 > N:
            sum_right = 0
        else:
            sum_right = (prefix_sum[j + s + 1] - prefix_sum[j + 1]) - current_A * s
        
        current_value = 2 * (sum_left + sum_right) - sum_total
        if current_value < min_val:
            min_val = current_value
    
    print(min_val)

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