結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
![]() |
提出日時 | 2024-01-14 03:30:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 351 ms / 2,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 520 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 146,652 KB |
最終ジャッジ日時 | 2025-03-14 12:20:59 |
合計ジャッジ時間 | 10,246 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
import sys input = sys.stdin.readline from bisect import bisect_left,bisect N,K=map(int,input().split()) TD=[list(map(int,input().split())) for i in range(N)] SUM=0 LIST=[] for t,d in TD: LIST.append(d) SUM+=d LIST.append(0) LIST.append(10**10) LIST=sorted(set(LIST)) OK=len(LIST)-1 NG=0 while OK>NG+1: mid=(OK+NG)//2 flag=0 x=-1<<30 for t,d in TD: if d>=LIST[mid]: if t-x<K: flag=1 break else: x=t if flag==0: OK=mid else: NG=mid DP=[(-2*10**9,0)] for t,d in TD: #print(DP) x=bisect(DP,(t-K,10**10))-1 #print(x) if d>LIST[OK-1]: a,b=DP[x] DP=[(-2000000000, 0),(t,d+b)] else: a,b=DP[x] DP.append((t,d+b)) #print(DP) while len(DP)>=2 and DP[-1][1]<=DP[-2][1]: DP.pop() print(LIST[OK-1]) print(SUM-DP[-1][1])