結果

問題 No.974 最後の日までに
ユーザー lam6er
提出日時 2025-04-16 00:22:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,866 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 96,252 KB
最終ジャッジ日時 2025-04-16 00:23:38
合計ジャッジ時間 6,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    W = int(sys.stdin.readline())
    weeks = [tuple(map(int, sys.stdin.readline().split())) for _ in range(W)]

    dp = [defaultdict(list) for _ in range(W + 2)]  # weeks 1 to W
    dp[1][False] = [(0, 0)]

    max_g = -float('inf')

    def add_to_dp(state_list, new_g, new_m):
        nonlocal max_g
        to_remove = []
        dominated = False
        for idx, (g, m) in enumerate(state_list):
            if g >= new_g and m >= new_m:
                dominated = True
                break
            if g <= new_g and m <= new_m:
                to_remove.append(idx)
        if dominated:
            return
        for idx in reversed(to_remove):
            del state_list[idx]
        state_list.append((new_g, new_m))

    for i in range(1, W + 1):
        current_dp = dp[i]
        for d in list(current_dp.keys()):
            pairs = current_dp[d]
            for g, m in pairs:
                a_i, b_i, c_i = weeks[i-1]

                # Action 1: Go to school
                if d:
                    new_g_act1 = g - 10**100
                    new_m_act1 = m
                    next_d_act1 = False
                else:
                    new_g_act1 = g
                    new_m_act1 = m
                    if i < W:
                        next_d_act1 = True
                    else:
                        next_d_act1 = False
                if i < W:
                    add_to_dp(dp[i+1][next_d_act1], new_g_act1, new_m_act1)
                else:
                    if new_m_act1 >= 0:
                        if new_g_act1 > max_g:
                            max_g = new_g_act1

                # Action 2: Work part-time
                if d:
                    new_g_act2 = g - 10**100
                    new_m_act2 = m + a_i
                else:
                    new_g_act2 = g
                    new_m_act2 = m + a_i
                next_d_act2 = False
                if i < W:
                    add_to_dp(dp[i+1][next_d_act2], new_g_act2, new_m_act2)
                else:
                    if new_m_act2 >= 0:
                        if new_g_act2 > max_g:
                            max_g = new_g_act2

                # Action 3: Date
                if d:
                    new_g_act3 = g + b_i
                    new_m_act3 = m - c_i
                else:
                    new_g_act3 = g
                    new_m_act3 = m
                next_d_act3 = False
                if i < W:
                    add_to_dp(dp[i+1][next_d_act3], new_g_act3, new_m_act3)
                else:
                    if new_m_act3 >= 0:
                        if new_g_act3 > max_g:
                            max_g = new_g_act3

    if max_g == -float('inf'):
        print(0)
    else:
        print(max_g)

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