Internet Problem Solving Contest

IPSC 2000

Solution to Problem R – Santo's Bottles

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

S1 = A1,
S2 = A1 + A2 and
S3 = max{A1 + A2, A1 + A3, A2 + A3}.

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

Sk = max{Sk-1, Sk-2 + Ak, Sk-3 + Ak-1 + Ak}.

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