結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:46:37
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,100 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 849,604 KB
最終ジャッジ日時 2025-03-31 17:47:35
合計ジャッジ時間 6,672 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from collections import defaultdict

    N = int(sys.stdin.readline())
    BC = []
    for _ in range(N):
        B, C = map(int, sys.stdin.readline().split())
        BC.append((B, C))
    M = int(sys.stdin.readline())
    constraints = [[] for _ in range(N)]  # constraints[i] contains list of j where i -> j
    for _ in range(M):
        D, E = map(int, sys.stdin.readline().split())
        constraints[D].append(E)

    # Memoization cache for the DP
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mask):
        if pos >= N:
            return 0
        # Decide whether to visit this country or not
        # Option 1: do not visit
        res = dp(pos + 1, mask)
        # Option 2: visit
        new_mask = mask
        must_join = (mask >> pos) & 1
        # If we are forced to join, then must choose B
        if must_join:
            # Choose to join
            score = BC[pos][0]
            next_mask = new_mask
            # Remove the current bit
            next_mask &= ~(1 << pos)
            # Apply new constraints
            for j in constraints[pos]:
                next_mask |= (1 << j)
            res = max(res, score + dp(pos + 1, next_mask))
        else:
            # Can choose to join or not, or skip visiting
            # Case 1: visit and not join
            score_not_join = BC[pos][1]
            new_mask_not_join = new_mask & ~(1 << pos)
            # Visit but not join: any future constraints not applied
            res_option = score_not_join + dp(pos + 1, new_mask_not_join)
            # Case 2: visit and join
            score_join = BC[pos][0]
            next_mask_join = new_mask
            next_mask_join &= ~(1 << pos)
            for j in constraints[pos]:
                next_mask_join |= (1 << j)
            res_option = max(res_option, score_join + dp(pos + 1, next_mask_join))
            # Take the best of visiting or not
            res = max(res, res_option)
        return res

    max_score = dp(0, 0)
    print(max_score)

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