This is a fast, linear solution (complexity O(N)) 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-2.rb

#####################################################################
#
# This is a fast, linear solution (complexity O(N)) 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
#
######################################################################


def calculate_max_gain(e, r, n, values)

  # For each value of the given array find the index
  # of the next value that is higher.  
  def get_next_higher_values(values, n)
    next_values = []
    n.times { next_values << nil }
    stack = []
    stack << { v: values.max, i: nil }
    for i in 0...n
      v = values[i]
      while v > stack[-1][:v]
        item = stack.pop
        next_values[item[:i]] = i
      end
      stack << { v: v, i: i}
    end
    return next_values
  end

  next_values = get_next_higher_values(values, n)

  max_gain = 0
  energy = e
  for i in 0...n
    if next_values[i].nil?
      max_gain += energy * values[i]
      energy = 0
    else
      next_i = next_values[i]
      e1 = e - r*(next_i - i)  # energy that needs to be left
      spe = [0, [energy, energy - e1].min].max
      max_gain += spe * values[i]
      energy -= spe
    end
    energy += r
    energy = e if energy > e
  end

  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 = calculate_max_gain(e, r, n, values) 
  puts "Case ##{t}: #{m}"
end