結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
![]() |
提出日時 | 2021-02-09 05:38:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 83,172 KB |
最終ジャッジ日時 | 2024-07-06 11:38:39 |
合計ジャッジ時間 | 8,677 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
n,k = map(int,input().split())t = [0]*nd = [0]*nfor i in range(n):t[i],d[i] = map(int,input().split())def check(x): #x以上を全部任せるが可能か?v = -1<<32for i in range(n):if d[i] >= x:if t[i]-v < k: return Falseelse: v = t[i]return Trueok = 10**9+1ng = 0while ok-ng > 1:mid = (ok+ng)//2if check(mid): ok = midelse: ng = midacc = [0]*(n+1)INF = 1<<40for i in range(n):if d[i] >= ok: d[i] = INFacc[i+1] += acc[i]+d[i]from bisect import bisect_leftdp2 = [0]*n #dp[i] = i 日目までの仕事の最小値for i in range(n):ti,di = t[i],d[i]idx = bisect_left(t,ti-k+1)x = (dp2[idx-1] if idx else 0) + acc[i] - acc[idx] #休むときdp2[i] = min(dp2[i-1]+di,x)print(ok-1)print(dp2[-1])