結果
問題 | No.1715 Dinner 2 |
ユーザー |
![]() |
提出日時 | 2021-11-14 22:57:41 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,297 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 300,908 KB |
最終ジャッジ日時 | 2024-11-30 08:59:12 |
合計ジャッジ時間 | 21,895 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 37 TLE * 1 |
ソースコード
from sys import stdin n, d, *indata = map(int, stdin.read().split()) offset = 0 p = [] q = [] for i in range(n): s, t = indata[offset + 2*i],indata[offset + 2*i+1] p.append(s) q.append(t) left = -10**8 right = 0 while (right - left) >= 2: mid = (right + left) // 2 dp = [[None for i in range(n)] for j in range(d)] for i in range(n): if -p[i] >= mid: dp[0][i] = q[i] - p[i] for i in range(1,d): ruisekileft = [-10**18 for i in range(n+1)] ruisekiright = [-10**18 for i in range(n+1)] for j in range(n): if dp[i-1][j] != None: ruisekileft[j+1] = max(ruisekileft[j],dp[i-1][j]) else: ruisekileft[j+1] = ruisekileft[j] if dp[i-1][n-j-1] != None: ruisekiright[j+1] = max(ruisekiright[j],dp[i-1][n-j-1]) else: ruisekiright[j+1] = ruisekiright[j] for j in range(n): kari = max(ruisekileft[j],ruisekiright[n-j-1]) if kari - p[j] >= mid: dp[i][j] = kari + q[j] - p[j] check = False for i in range(n): if dp[d-1][i] != None: check = True break if check: left = mid else: right = mid print("{}".format(left))