Submission #2548436

---

Source Code Expand

N, K = gets.split.map(&:to_i)
as = N.times.map{gets.to_i}
asum = as.dup
(N-1).times do |i|
    asum[i+1] += asum[i]
end

if K == 0
    puts 0
    exit
elsif K == asum[N-1]
    puts 1
    exit
end

BIG = K+1

dp = Array.new(N){Array.new(N+1, BIG)}
dp[0][0] = 0
dp[0][1] = 1
(1...N).each do |i|
    (1..(i+1)).each do |j|
        dp[i][j] = dp[i-1][j]
        d2 = dp[i-1][j-1]*asum[i]/asum[i-1] + 1
        if d2 <= K && d2 - dp[i-1][j-1] <= as[i] && d2 < dp[i][j]
            dp[i][j] = d2
        end
    end
end

puts (0..N).select{|i|dp[N-1][i] < BIG}.max

Submission Info

Judge Result