Internet Problem Solving Contest

• Program solving both data sets

Let's mark A_k the volume of Santo's k-th bottle in the row and S_k the maximal volume of alcohol Santo can drink while drinking only from first k bottles. Obviously:

S₁ = A₁,
S₂ = A₁ + A₂ and
S₃ = max{A₁ + A₂, A₁ + A₃, A₂ + A₃}.

Now, for some k (4 ≤= k ≤= N) let's assume that we know all the numbers S₁, S₂, ... S_k-1. From the problem description is easy to figure out that

S_k = max{S_k-1, S_k-2 + A_k, S_k-3 + A_k-1 + A_k}.

What is an easy recurent formula, which can be computed straightforward in one loop.