結果

問題 No.1522 Unfairness
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:59:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,344 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 467,196 KB
最終ジャッジ日時 2025-03-26 16:00:53
合計ジャッジ時間 17,044 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# Initialize DP: dp[i][cost] = max O
dp = [{} for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    current_dp = dp[i]
    if not current_dp:
        continue
    # Option 1: skip the current element
    for cost in current_dp:
        o_val = current_dp[cost]
        next_i = i + 1
        if next_i <= n:
            if cost in dp[next_i]:
                if o_val > dp[next_i][cost]:
                    dp[next_i][cost] = o_val
            else:
                dp[next_i][cost] = o_val
    # Option 2: pair current with next element
    if i + 1 >= n:
        continue
    pair_cost = a[i] - a[i+1]
    for cost in current_dp:
        o_val = current_dp[cost]
        new_cost = cost + pair_cost
        if new_cost > m:
            continue
        new_o = o_val + a[i]
        next_i_paired = i + 2
        if next_i_paired > n:
            continue
        if new_cost in dp[next_i_paired]:
            if new_o > dp[next_i_paired][new_cost]:
                dp[next_i_paired][new_cost] = new_o
        else:
            dp[next_i_paired][new_cost] = new_o

# Find the maximum O where cost <= m
max_o = 0
for i in range(n+1):
    for cost in dp[i]:
        if cost <= m and dp[i][cost] > max_o:
            max_o = dp[i][cost]

print(max_o)
0