結果

問題 No.771 しおり
コンテスト
ユーザー Nikkuniku029
提出日時 2022-11-04 11:55:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 746 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 302,208 KB
最終ジャッジ日時 2024-07-18 12:18:43
合計ジャッジ時間 6,899 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
books = [list(map(int, input().split())) for _ in range(N)]


def isOK(k):
    dp = [[False]*N for _ in range(1 << N)]
    for i in range(N):
        dp[1 << i][i] = True

    for s in range(1 << N):
        for u in range(N):
            if not s & (1 << u) and s != 0:
                continue
            if not dp[s][u]:
                continue
            for v in range(N):
                if s & (1 << v):
                    continue
                if books[u][1]-books[u][0]+books[v][0] > k:
                    continue
                dp[s | (1 << v)][v] |= dp[s][u]

    return sum(dp[-1]) > 0


l = 0
r = 17002
while r-l > 1:
    mid = (l+r)//2
    if isOK(mid):
        r = mid
    else:
        l = mid
print(r)
0