結果

問題 No.974 最後の日までに
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:48:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,114 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 152,316 KB
最終ジャッジ日時 2025-03-26 15:50:08
合計ジャッジ時間 6,908 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    W = int(sys.stdin.readline())
    abc = [list(map(int, sys.stdin.readline().split())) for _ in range(W)]
    
    dp = defaultdict(list)
    dp[(1, 0)] = [(0, 0)]
    
    for i in range(1, W + 1):
        for s in [0, 1]:
            current_key = (i, s)
            if current_key not in dp:
                continue
            current_list = dp[current_key]
            for (good, money) in current_list:
                if s == 0:
                    # Action 1: Work
                    new_good = good
                    new_money = money + abc[i-1][0]
                    next_i = i + 1
                    next_s = 0
                    add_state(dp, next_i, next_s, new_good, new_money)
                    
                    # Action 2: School
                    if i < W:
                        next_i_school = i + 2
                        next_s_school = 0
                        b = abc[i][1]
                        c = abc[i][2]
                        new_good_school = good + b
                        new_money_school = money - c
                        add_state(dp, next_i_school, next_s_school, new_good_school, new_money_school)
                    else:
                        next_i_school = i + 1
                        next_s_school = 0
                        new_good_school = good
                        new_money_school = money
                        add_state(dp, next_i_school, next_s_school, new_good_school, new_money_school)
                    
                    # Action 3: Date (no effect)
                    new_good_date = good
                    new_money_date = money
                    next_i_date = i + 1
                    next_s_date = 0
                    add_state(dp, next_i_date, next_s_date, new_good_date, new_money_date)
                else:
                    # Forced to date
                    b = abc[i-1][1]
                    c = abc[i-1][2]
                    new_good = good + b
                    new_money = money - c
                    next_i = i + 1
                    next_s = 0
                    add_state(dp, next_i, next_s, new_good, new_money)
    
    max_good = 0
    for key in dp:
        i, s = key
        if i > W:
            for g, m in dp[key]:
                if m >= 0 and g > max_good:
                    max_good = g
    print(max_good)

def add_state(dp_dict, next_i, next_s, new_good, new_money):
    key = (next_i, next_s)
    new_list = []
    added = False
    for g, m in dp_dict.get(key, []):
        if g >= new_good and m >= new_money:
            added = True
            break
        if not (new_good >= g and new_money >= m):
            new_list.append((g, m))
    if not added:
        new_list.append((new_good, new_money))
        new_list.sort(key=lambda x: (-x[0], -x[1]))
        filtered = []
        max_m = -float('inf')
        for g, m in new_list:
            if m > max_m:
                filtered.append((g, m))
                max_m = m
        dp_dict[key] = filtered

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