結果

問題 No.974 最後の日までに
ユーザー gew1fw
提出日時 2025-06-12 20:46:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,374 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,652 KB
実行使用メモリ 571,896 KB
最終ジャッジ日時 2025-06-12 20:47:25
合計ジャッジ時間 6,757 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    W = int(sys.stdin.readline())
    weeks = []
    for _ in range(W):
        a, b, c = map(int, sys.stdin.readline().split())
        weeks.append((a, b, c))
    
    # Initialize DP: dp[i][prev] is a dict {money: max_goodwill}
    # prev is 0 (False), 1 (True)
    dp = [ [{} for _ in range(2)] for __ in range(W + 2)]
    dp[1][0][0] = 0  # starting point: week 1, no appointment, money 0, goodwill 0

    for i in range(1, W + 1):
        a_i, b_i, c_i = weeks[i - 1]
        for prev in [0, 1]:
            current_dp = dp[i][prev]
            if not current_dp:
                continue
            for m in list(current_dp.keys()):
                current_g = current_dp[m]
                # Consider each possible action
                if prev == 0:
                    # Option 1: choose school (only possible if prev is False)
                    if i < W:
                        new_prev = 1
                        new_m = m
                        new_g = current_g
                        if new_m in dp[i+1][new_prev]:
                            if new_g > dp[i+1][new_prev][new_m]:
                                dp[i+1][new_prev][new_m] = new_g
                        else:
                            dp[i+1][new_prev][new_m] = new_g
                    # Option 2: choose work (only possible if prev is False)
                    new_prev = 0
                    new_m_work = m + a_i
                    new_g_work = current_g
                    if i < W:
                        if new_m_work in dp[i+1][new_prev]:
                            if new_g_work > dp[i+1][new_prev][new_m_work]:
                                dp[i+1][new_prev][new_m_work] = new_g_work
                        else:
                            dp[i+1][new_prev][new_m_work] = new_g_work
                    else:
                        # i == W, check if new_m_work >= 0
                        if new_m_work >= 0:
                            if new_g_work > current_g:
                                pass  # since current_g is already considered
                            # Record the maximum goodwill
                            if new_g_work > dp[i+1][new_prev].get(new_m_work, -float('inf')):
                                dp[i+1][new_prev][new_m_work] = new_g_work
                else:
                    # prev is True, can choose date
                    # Option 3: choose date (only possible if prev is True)
                    new_prev = 0
                    new_m_date = m - c_i
                    new_g_date = current_g + b_i
                    if i < W:
                        if new_m_date in dp[i+1][new_prev]:
                            if new_g_date > dp[i+1][new_prev][new_m_date]:
                                dp[i+1][new_prev][new_m_date] = new_g_date
                        else:
                            dp[i+1][new_prev][new_m_date] = new_g_date
                    else:
                        # i == W, check if new_m_date >=0
                        if new_m_date >= 0:
                            if new_g_date > dp[i+1][new_prev].get(new_m_date, -float('inf')):
                                dp[i+1][new_prev][new_m_date] = new_g_date
                # Additionally, handle i=W for other actions
                if i == W:
                    # For work action
                    if prev == 0:
                        new_m_work = m + a_i
                        new_g_work = current_g
                        if new_m_work >= 0:
                            if new_g_work > dp[i+1][0].get(new_m_work, -float('inf')):
                                dp[i+1][0][new_m_work] = new_g_work
                    # For date action
                    if prev == 1:
                        new_m_date = m - c_i
                        new_g_date = current_g + b_i
                        if new_m_date >= 0:
                            if new_g_date > dp[i+1][0].get(new_m_date, -float('inf')):
                                dp[i+1][0][new_m_date] = new_g_date
    
    max_goodwill = -float('inf')
    for prev in [0, 1]:
        for m, g in dp[W+1][prev].items():
            if m >= 0:
                if g > max_goodwill:
                    max_goodwill = g
    if max_goodwill == -float('inf'):
        print(0)
    else:
        print(max_goodwill)

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