## IPSC 2000

## Solution to Problem R – Santo's Bottles

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**_{1} = A_{1},

**S**_{2} = A_{1} + A_{2} and

**S**_{3} = max{A_{1} + A_{2},
A_{1} + A_{3}, A_{2} + A_{3}}.

Now, for some **k** (**4 ≤= k ≤= N**) let's assume that
we know all the numbers **S**_{1}, **S**_{2}, ...
**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.