結果
問題 | No.771 しおり |
ユーザー |
|
提出日時 | 2021-05-19 11:01:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,508 ms / 2,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 81,784 KB |
実行使用メモリ | 145,128 KB |
最終ジャッジ日時 | 2024-07-22 07:27:16 |
合計ジャッジ時間 | 24,165 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#region Header#!/usr/bin/env python3# from typing import *import sysimport ioimport mathimport collectionsimport decimalimport itertoolsimport bisectimport heapqdef input():return sys.stdin.readline()[:-1]# sys.setrecursionlimit(1000000)#endregion# _INPUT = """3# 1 4# 2 4# 3 4# """# sys.stdin = io.StringIO(_INPUT)def main():N = int(input())A = [None for _ in range(N)]B = [None for _ in range(N)]for i in range(N):A[i], B[i] = map(int, input().split())dp = [[10**10] * N for _ in range(1<<N)]for i in range(N):dp[1<<i][i] = 0for s in range(1<<N):for k in range(N):if not(s & (1<<k)):continuefor i in range(N):if s & (1<<i):continuev1 = max(dp[s][k], B[k] - A[k] + A[i])s1 = s | (1<<i)dp[s1][i] = min(dp[s1][i], v1)ans = min(dp[(1<<N)-1])print(ans)if __name__ == '__main__':main()