結果

問題 No.1522 Unfairness
ユーザー gew1fw
提出日時 2025-06-12 21:25:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,327 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 92,416 KB
最終ジャッジ日時 2025-06-12 21:26:44
合計ジャッジ時間 3,966 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    A.sort(reverse=True)
    
    max_k = N // 2
    INF = -float('inf')
    
    # Initialize DP
    dp = [ [INF]*(M+1) for _ in range(max_k+1) ]
    dp[0][0] = 0
    
    for i in range(0, N-1):
        for j in range(max_k, -1, -1):
            for d in range(M, -1, -1):
                if dp[j][d] == INF:
                    continue
                if j >= max_k:
                    continue
                new_j = j + 1
                dx = A[i] - A[i+1]
                new_d = d + dx
                if new_d > M:
                    continue
                new_sum = dp[j][d] + A[i] + A[i+1]
                if new_sum > dp[new_j][new_d]:
                    dp[new_j][new_d] = new_sum
        # Merge i and i+1 as processed
        # No need to do anything else, since i increases by 1
    
    max_O = 0
    for j in range(0, max_k+1):
        for d in range(0, M+1):
            if dp[j][d] == INF:
                continue
            sum_selected = dp[j][d]
            sum_x = (sum_selected + d) // 2
            if sum_x > max_O:
                max_O = sum_x
    print(max_O)

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