結果
問題 | No.1715 Dinner 2 |
ユーザー |
![]() |
提出日時 | 2021-10-22 22:04:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 601 ms / 2,000 ms |
コード長 | 728 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 81,992 KB |
実行使用メモリ | 77,052 KB |
最終ジャッジ日時 | 2024-09-23 05:35:10 |
合計ジャッジ時間 | 8,860 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
n, d = map(int, input().split()) pq = list(tuple(map(int, input().split())) for _ in range(n)) l = -10 ** 9 r = 0 while r - l > 1: c = (l + r) // 2 dp = [0] * n for _ in range(d): ndp = [-10 ** 9] * n mx = -10 ** 9 - 1 imx = -1 for i in range(n): if dp[i] > mx: mx = dp[i] imx = i for i, (p, q) in enumerate(pq): if i != imx and mx - p >= c: ndp[i] = mx - p + q p, q = pq[imx] for i in range(n): if i != imx and dp[i] - p >= c: ndp[imx] = max(ndp[imx], dp[i] - p + q) dp = ndp if max(dp) == -10 ** 9: r = c else: l = c print(l)