結果

問題 No.3513 Greedy Yokan Party
コンテスト
ユーザー tomerun
提出日時 2026-04-24 21:49:05
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 907 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,468 ms
コンパイル使用メモリ 338,844 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-24 21:49:35
合計ジャッジ時間 26,162 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 2 OLE * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n, l = read_line.split.map(&.to_i)
k = read_line.to_i
a = [0] + read_line.split.map(&.to_i) + [l]

lo = 1
hi = l
while hi - lo > 1
  mid = (lo + hi) // 2
  if ok(mid, a, l, k)
    lo = mid
  else
    hi = mid
  end
end
puts lo

def ok(len, a, l, k)
  n = a.size
  bc = Array.new(n, n + 1)
  right = n - 1
  left = n - 1
  while a[right] - a[left] < len
    left -= 1
  end
  while true
    bc[left] = right - left - 1
    break if left == 0
    left -= 1
    while a[right - 1] - a[left] >= len
      right -= 1
    end
  end
  (n - 2).downto(0) do |i|
    bc[i] = {bc[i], bc[i + 1]}.min
  end
  puts [len, bc]
  left = 0
  right = 1
  while a[right] - a[left] < len
    right += 1
  end
  while right < n - 1
    fc = right - left - 1
    if fc + bc[right + 1] <= (n - 2) - k
      return true
    end
    right += 1
    while a[right] - a[left + 1] >= len
      left += 1
    end
  end
  return false
end
0