Submission #801003

---

Source Code Expand

# coding: utf-8
nk = gets.split
N = nk[0].to_i
K = nk[1].to_i

if K == 0
  puts 0
  exit
end

sigma_a = [0]
last_an = nil
N.times do
  last_an = a = gets.to_i
  sigma_a.push sigma_a[sigma_a.length - 1] + a
end

w = Array.new(N+1).map { Array.new(N+1, -1) }

# x: n日目, y: 機嫌がいい日の総数
# w[x][y]: n日目にy日機嫌がよくなるような最小勝数
(N+1).times do |x|
  if x == 0
    w[0][0] = 0
    next
  end

  w[x][0] = 0
  w[x][1] = 1
  y = 2
  while(y <= x)
    value = ((w[x-1][y-1] * sigma_a[x]).to_f / sigma_a[x-1])
    if value.ceil == value.floor
      value = value.ceil + 1
    else
      value = value.ceil
    end


    if value > w[x-1][y] && w[x-1][y] > -1
      value = w[x-1][y]
    end

    break if value > K
    
    # 最終日の場合、少なくとも全勝して総勝数 == Kにならなければいけない
    if x < N || (x == N && w[x-1][y-1] + last_an >= K)
      w[x][y] = value
    end

    y += 1
  end
end
  
max = 0
(N+1).times do |i|
  max = i if w[N][i] > -1 && w[N][i] <= K
end

puts max

Submission Info

Judge Result