結果

問題 No.1522 Unfairness
コンテスト
ユーザー lam6er
提出日時 2025-03-31 18:00:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,658 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 77,252 KB
最終ジャッジ日時 2025-03-31 18:02:04
合計ジャッジ時間 4,016 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

k_max = n // 2
sum_initial_O = [0] * (k_max + 1)
sum_d_initial = [0] * (k_max + 1)

for k in range(1, k_max + 1):
    sum_initial_O[k] = sum_initial_O[k-1] + A[2*(k-1)]
    sum_d_initial[k] = sum_d_initial[k-1] + (A[2*(k-1)] - A[2*(k-1)+1])

max_result = 0

# Check all possible k from largest to smallest
for k in range(k_max, 0, -1):
    current_initial_O = sum_initial_O[k]
    current_sum_d = sum_d_initial[k]
    
    if current_sum_d <= m:
        if current_initial_O > max_result:
            max_result = current_initial_O
        # Since this is the largest k possible, no need to check smaller k
        break
    else:
        required_reduction = current_sum_d - m
        required_d_sum = (required_reduction + 1) // 2
        
        # Generate the list of d values for this k
        d_list = []
        for i in range(k):
            d = A[2*i] - A[2*i + 1]
            d_list.append(d)
        # Sort d in descending order
        d_list_sorted = sorted(d_list, reverse=True)
        
        # Compute prefix sums
        prefix_sum = [0]
        for d in d_list_sorted:
            prefix_sum.append(prefix_sum[-1] + d)
        
        # Find the minimal t where prefix_sum[t] >= required_d_sum
        t = bisect.bisect_left(prefix_sum, required_d_sum)
        if t <= len(prefix_sum) - 1:
            current_candidate = current_initial_O - prefix_sum[t]
            if current_candidate > max_result:
                max_result = current_candidate

# Check k = 0 case (O is 0)
max_result = max(max_result, 0)

print(max_result)
0