結果

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

ソースコード

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
  left = 0
  right = 1
  while a[right] - a[left] < len
    right += 1
  end
  while true
    fc = right - left - 1
    if fc + bc[right] <= (n - 2) - k
      return true
    end
    break if right == n - 1
    right += 1
    while a[right] - a[left + 1] >= len
      left += 1
    end
  end
  return false
end
0