結果

問題 No.1522 Unfairness
ユーザー lam6er
提出日時 2025-03-31 17:56:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 464 ms / 2,000 ms
コード長 1,156 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 147,388 KB
最終ジャッジ日時 2025-03-31 17:57:40
合計ジャッジ時間 5,511 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

max_oe = M
max_index = n

# Initialize DP table: dp[i][m] represents the maximum O sum considering first i elements and unfairness m.
dp = [[-1 for _ in range(max_oe + 1)] for _ in range(n + 2)]
dp[0][0] = 0

for i in range(n + 1):
    for current_oe in range(max_oe + 1):
        if dp[i][current_oe] == -1:
            continue
        # Option 1: Do not pick the current element (if there is one)
        if i < n:
            if dp[i + 1][current_oe] < dp[i][current_oe]:
                dp[i + 1][current_oe] = dp[i][current_oe]
        # Option 2: Pick the current and next element as a pair (if possible)
        if i + 1 < n:
            ai = a[i]
            aj = a[i + 1]
            new_oe = current_oe + (ai - aj)
            new_o = dp[i][current_oe] + ai
            if new_oe <= max_oe and new_o > dp[i + 2][new_oe]:
                dp[i + 2][new_oe] = new_o

# Find the maximum O across all possible dp states
max_o = 0
for i in range(n + 2):
    for oe in range(max_oe + 1):
        if dp[i][oe] > max_o:
            max_o = dp[i][oe]

print(max_o)
0