結果
問題 | No.1715 Dinner 2 |
ユーザー |
![]() |
提出日時 | 2021-10-22 22:34:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,248 ms / 2,000 ms |
コード長 | 1,017 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 77,260 KB |
最終ジャッジ日時 | 2024-09-23 06:16:47 |
合計ジャッジ時間 | 14,555 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
n,d=map(int,input().split()) p=[] q=[] for i in range(n): a,b=map(int,input().split()) p.append(a) q.append(b) def f(x): dp=[-10**18]*n for i in range(n): if -p[i]>=x:dp[i]=-p[i]+q[i] maxdp1=[-10**18]*(n+1) maxdp2=[-10**18]*(n+1) for i in range(n): maxdp1[i]=max(maxdp1[i-1],dp[i]) for i in range(n-1,-1,-1): maxdp2[i]=max(maxdp2[i+1],dp[i]) for _ in range(d-1): for i in range(n): res=max(maxdp1[i-1],maxdp2[i+1]) if res-p[i]>=x: dp[i]=res-p[i]+q[i] else:dp[i]=-10**18 for i in range(n): maxdp1[i] = max(maxdp1[i - 1], dp[i]) for i in range(n - 1, -1, -1): maxdp2[i] = max(maxdp2[i + 1], dp[i]) for i in range(n): if dp[i]>-10**18:return True return False ok = -10 ** 18 ng = 0 while ng - ok > 1: mid = (ok + ng) // 2 if f(mid): ok = mid else: ng = mid print(ok)