結果

問題 No.974 最後の日までに
ユーザー gew1fw
提出日時 2025-06-12 13:20:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,050 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 100,776 KB
最終ジャッジ日時 2025-06-12 13:22:43
合計ジャッジ時間 6,715 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    W = int(input[idx])
    idx += 1
    weeks = []
    for _ in range(W):
        a = int(input[idx])
        b = int(input[idx+1])
        c = int(input[idx+2])
        weeks.append((a, b, c))
        idx += 3

    # Initialize DP
    dp = [{} for _ in range(W + 1)]
    dp[0][0] = [(0, 0)]
    dp[0][1] = []

    def prune(pairs):
        groups = {}
        for g, m in pairs:
            if g not in groups or m > groups[g]:
                groups[g] = m
        sorted_pairs = sorted(groups.items(), key=lambda x: x[0])
        pruned = []
        n = len(sorted_pairs)
        for i in range(n):
            g_i, m_i = sorted_pairs[i]
            dominated = False
            for j in range(n):
                if i == j:
                    continue
                g_j, m_j = sorted_pairs[j]
                if g_j >= g_i and m_j >= m_i:
                    dominated = True
                    break
            if not dominated:
                pruned.append((g_i, m_i))
        return pruned

    for i in range(1, W + 1):
        current_week = i
        a_i, b_i, c_i = weeks[i-1]
        new_dp = {0: [], 1: []}
        for p_prev in [0, 1]:
            if p_prev not in dp[i-1]:
                continue
            for (g_prev, m_prev) in dp[i-1][p_prev]:
                # Action 1: School
                if p_prev == 1:
                    new_g = g_prev - 10**100
                    new_m = m_prev
                    new_p = 0
                else:
                    if current_week < W:
                        new_g = g_prev
                        new_m = m_prev
                        new_p = 1
                    else:
                        new_g = g_prev
                        new_m = m_prev
                        new_p = 0
                new_dp[new_p].append((new_g, new_m))
                # Action 2: Part-time
                if p_prev == 1:
                    new_g_p = g_prev - 10**100
                    new_m_p = m_prev + a_i
                else:
                    new_g_p = g_prev
                    new_m_p = m_prev + a_i
                new_p_p = 0
                new_dp[new_p_p].append((new_g_p, new_m_p))
                # Action 3: Date
                if p_prev == 1:
                    new_g_d = g_prev + b_i
                    new_m_d = m_prev - c_i
                else:
                    new_g_d = g_prev
                    new_m_d = m_prev
                new_p_d = 0
                new_dp[new_p_d].append((new_g_d, new_m_d))
        # Prune the new_dp entries
        for p in [0, 1]:
            new_dp[p] = prune(new_dp[p])
        dp[i] = new_dp

    # Collect all possible pairs from week W's states 0 and 1
    candidates = []
    for p in [0, 1]:
        if p in dp[W]:
            for (g, m) in dp[W][p]:
                if m >= 0:
                    candidates.append(g)
    if not candidates:
        print(0)
    else:
        print(max(candidates))

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