This is a recursive solution of Problem B, Manage your Energy, of Round 1B 2013 on Google CodeJam. * Problem description: https://code.google.com/codejam/contest/2418487/dashboard#s=p1&a=1 * Solution Description: https://code.google.com/codejam/contest/2418487/dashboard#s=a&a=1

energy-1.rb

#####################################################################
#
# This is a recursive solution of Problem B, Manage your Energy,
# of Round 1B 2013 on Google CodeJam.
# 
# * Problem description:
#   https://code.google.com/codejam/contest/2418487/dashboard#s=p1&a=1
# * Solution Description:
#   https://code.google.com/codejam/contest/2418487/dashboard#s=a&a=1
#
######################################################################

# We start processing the array of values by having
# an initial energy of 'e_initial'. After processing
# the array of values we must still have 'e_remaining'
# energy left.
def maximum_gain(e, r, values, e_initial, e_remaining)
  return 0 if values == []

  # find max value and its index
  v_max = values.max
  i = values.index(v_max)
  # split the array of values at the max value
  values_prev = (i==0 ? [] : values[0 .. i-1])
  values_next = values[i+1 .. -1]

  # calculate the max energy that we can spend on v_max
  e1 = e_initial + r*values_prev.length
  e1 = [e1, e].min
  e2 = e_remaining - r*values_next.length
  e2 = [e2, 0].max

  # calculate the max gain recursively
  max_gain = v_max * (e1 - e2)
  max_gain += maximum_gain(e, r, values_prev, e_initial, [e1-r, 0].max)
  max_gain += maximum_gain(e, r, values_next, [e2+r, e].min, e_remaining)

  return max_gain
end

T = gets.to_i
for t in 1..T
  e, r, n = gets.chomp.split.map { |x| x.to_i }
  r = [e, r].min
  values = gets.chomp.split.map { |x| x.to_i }

  m = maximum_gain(e, r, values, e, 0)
  puts "Case ##{t}: #{m}"
end