結果
問題 | No.1715 Dinner 2 |
ユーザー |
|
提出日時 | 2022-01-22 10:25:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,059 ms / 2,000 ms |
コード長 | 941 bytes |
コンパイル時間 | 630 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 275,584 KB |
最終ジャッジ日時 | 2024-11-27 04:22:28 |
合計ジャッジ時間 | 12,733 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
N, D = map(int, input().split()) INF = 1 << 60 p = [] q = [] for _ in range(N): s, t = map(int, input().split()) p.append(s) q.append(t) def solve(x): dp = [[-INF] * 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 = [-INF for _ in range(N + 1)] ra = [-INF 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] != -INF: 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)