結果
問題 |
No.1715 Dinner 2
|
ユーザー |
|
提出日時 | 2022-01-22 10:38:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,146 ms / 2,000 ms |
コード長 | 900 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 275,200 KB |
最終ジャッジ日時 | 2024-11-27 04:39:20 |
合計ジャッジ時間 | 13,951 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
import sys N, D, *data = map(int, sys.stdin.read().split()) MINF = -(10 ** 9) p = data[::2] q = data[1::2] def solve(x): dp = [[MINF] * N for _ in range(D)] for i in range(N): if -p[i] >= x: dp[0][i] = q[i] - p[i] for i in range(1, D): la = [MINF for _ in range(N + 1)] ra = [MINF for _ in range(N + 1)] for j in range(N): la[j + 1] = max(la[j], dp[i - 1][j]) ra[j + 1] = max(ra[j], dp[i - 1][N - j - 1]) for j in range(N): tmp = max(la[j], ra[N - j - 1]) if tmp - p[j] >= x: dp[i][j] = tmp - p[j] + q[j] for i in range(N): if dp[D - 1][i] != MINF: return True return False left = -(10 ** 8) right = 0 while right - left > 1: mid = (right + left) // 2 if solve(mid): left = mid else: right = mid print(left)