結果

問題 No.951 【本日限定】１枚頼むともう１枚無料！
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:30:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,240 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 267,044 KB
最終ジャッジ日時 2025-04-24 12:33:33
合計ジャッジ時間 74,108 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 TLE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    K = int(input[idx+1])
    idx +=2
    pizzas = []
    for _ in range(N):
        P = int(input[idx])
        D = int(input[idx+1])
        pizzas.append((-P, -D))  # Sort by descending P, then descending D
        idx +=2
    pizzas.sort()
    # Convert back to positive
    pizzas = [(-p, -d) for (p, d) in pizzas]
    
    # Initialize DP: dictionary of (cost, state) to max_deliciousness
    dp = [ [-1]*(2) for _ in range(K+1) ]
    dp[0][0] = 0  # initial state: cost 0, state 0
    
    for (p, d) in pizzas:
        # Create a new temporary DP
        new_dp = [ row[:] for row in dp ]  # copy current state
        for cost in range(K+1):
            for state in [0, 1]:
                current_d = dp[cost][state]
                if current_d == -1:
                    continue
                # Option 1: Pay for this pizza if state is 0
                if state == 0:
                    new_cost = cost + p
                    if new_cost <= K:
                        if new_dp[new_cost][1] < current_d + d:
                            new_dp[new_cost][1] = current_d + d
                # Option 2: If state is 1, take this pizza as free
                if state == 1:
                    # Take as free
                    if new_dp[cost][0] < current_d + d:
                        new_dp[cost][0] = current_d + d
                    # Pay for this pizza (without taking free)
                    new_cost_pay = cost + p
                    if new_cost_pay <= K:
                        if new_dp[new_cost_pay][1] < current_d + d:
                            new_dp[new_cost_pay][1] = current_d + d
                    # Do not pay and do not take free (state becomes 0)
                    if new_dp[cost][0] < current_d:
                        new_dp[cost][0] = current_d
        # Update dp to new_dp
        dp = new_dp
    
    # Find the maximum deliciousness across all possible costs and states
    max_del = 0
    for cost in range(K+1):
        for state in [0, 1]:
            if dp[cost][state] > max_del:
                max_del = dp[cost][state]
    print(max_del)

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