結果

問題 No.1715 Dinner 2
ユーザー lam6er
提出日時 2025-03-20 20:42:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,451 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 91,020 KB
最終ジャッジ日時 2025-03-20 20:42:40
合計ジャッジ時間 4,320 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    n, d = map(int, sys.stdin.readline().split())
    dishes = []
    for _ in range(n):
        p, q = map(int, sys.stdin.readline().split())
        dishes.append((p, q))
    
    # Initialize for day 1
    dp = [{} for _ in range(d + 1)]
    for j in range(n):
        p, q = dishes[j]
        e = -p + q
        m = -p
        dp[1][j] = [(e, m)]
    
    for day in range(2, d + 1):
        curr = {}
        for prev_dish in dp[day - 1]:
            prev_states = dp[day - 1][prev_dish]
            for (e_prev, m_prev) in prev_states:
                for j in range(n):
                    if j == prev_dish:
                        continue
                    p_j, q_j = dishes[j]
                    new_cook = e_prev - p_j
                    new_min = min(m_prev, new_cook)
                    new_e = new_cook + q_j
                    
                    if j not in curr:
                        curr[j] = []
                    candidates = curr[j]
                    to_add = True
                    to_remove = []
                    for idx in reversed(range(len(candidates))):
                        e_exist, m_exist = candidates[idx]
                        if e_exist >= new_e and m_exist >= new_min:
                            to_add = False
                            break
                        if new_e >= e_exist and new_min >= m_exist:
                            to_remove.append(idx)
                    if to_add:
                        for idx in to_remove:
                            del candidates[idx]
                        candidates.append((new_e, new_min))
                        # Check if new entry dominates others
                        new_remove = []
                        for idx in reversed(range(len(candidates) - 1)):
                            e_exist, m_exist = candidates[idx]
                            if new_e >= e_exist and new_min >= m_exist:
                                new_remove.append(idx)
                        for idx in new_remove:
                            del candidates[idx]
                    else:
                        pass
        dp[day] = curr
    
    max_min = -float('inf')
    if d == 0:
        print(0)
        return
    
    for states in dp[d].values():
        for (e, m) in states:
            if m > max_min:
                max_min = m
    
    print(max_min)

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