結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
|
提出日時 | 2016-11-23 01:14:46 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 749 ms / 2,000 ms |
コード長 | 619 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 28,288 KB |
最終ジャッジ日時 | 2024-06-11 19:36:14 |
合計ジャッジ時間 | 14,684 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
コンパイルメッセージ
Syntax OK
ソースコード
#!/usr/bin/rubyn,k=gets.split.map(&:to_i)a=$<.map{|e|e.split.map(&:to_i)}p ma=(0..10**9).bsearch{|e|tail=-k!!a.each{|t,d|if d>eif t-tail<kbreakelsetail=tendend}}ng=[false]*ntail=-k0.upto(n-1){|i|if a[i][1]>matail=a[i][0]elsif a[i][0]-tail<kng[i]=trueend}tail=a[-1][0]+k(n-1).downto(0){|i|if a[i][1]>matail=a[i][0]elsif tail-a[i][0]<kng[i]=trueend}s=0n.times{|i|if a[i][1]>maa[i][1]=0elses+=a[i][1]a[i][1]=0 if ng[i]end}dp=[0]t=x=0n.times{|i|t=[t,dp[x+=1]].max while a[i][0]-a[x][0]>=kdp[i+1]=[dp[i],t+a[i][1]].max}p s-dp[n]