結果

問題 No.3537 Thank You!
コンテスト
ユーザー tomerun
提出日時 2026-05-08 22:07:38
言語 Crystal
(1.19.1)
コンパイル:
crystal build -Donline_judge -o a.out --release --no-debug _filename_
実行:
./a.out
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 955 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,304 ms
コンパイル使用メモリ 342,872 KB
実行使用メモリ 18,432 KB
最終ジャッジ日時 2026-05-08 22:07:53
合計ジャッジ時間 12,998 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サブタスク1 30 % AC * 21
サブタスク2 70 % AC * 15
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = read_line.to_i
b = read_line.to_i64
cs = [] of Tuple(Int64, Int64)
c = read_line.split.map(&.to_i64)
s = read_line.split.map(&.to_i64)
n.times do |i|
  cs << {c[i], s[i]}
end
cs.sort!
pos = 0
ans = 0
tb = b
n.times do |i|
  if tb < cs[i][0] * cs[i][1]
    ans += tb // cs[i][0]
    break
  end
  tb -= cs[i][0] * cs[i][1]
  ans += cs[i][1]
  pos += 1
end
if pos == n
  puts ans
  exit
end

if pos > 0
  idx = (0...pos).max_by { |i| (cs[i][0] - 1) * cs[i][1] }
  ans = {ans, solve(cs, b, idx)}.max
end
ans = {ans, solve(cs, b, pos)}.max
if pos < n - 1
  idx = (pos...n).max_by { |i| cs[i][1] }
  ans = {ans, solve(cs, b, idx)}.max
end
puts ans

def solve(cs, b, idx)
  if b < cs[idx][1]
    ta = b
  else
    ta = cs[idx][1]
    tb = b - ta
    cs.size.times do |i|
      next if i == idx
      if tb < cs[i][0] * cs[i][1]
        ta += tb // cs[i][0]
        break
      end
      tb -= cs[i][0] * cs[i][1]
      ta += cs[i][1]
    end
  end
  ta
end
0