# SPOJ CHOCOLA

## 203 (POTHOLE) - Potholers[edit]

## Summary[edit]

Compute the minimal cost of breaking the whole chocolate into single squares.

## Explanation[edit]

After careful observation you can see that you must always choose line with highest cost. Explanation for this is: Every time you choose to break a chocolate the cost of next breaks will increase, so it's pretty clear that we must first break the lines with highest cost.

The next observation is that, if equals , it doesn't matter which one you choose because the sum of these breaks will be the same. To see why this is true lets look at this example: Input:

2 2 2 2

As you can see equals . If you choose to break first the total cost will be '2 + 2*2', and the same will go for if you decide to break first. So the final conclusion is that cost of vertical breaking is:

And the same goes for horizontal breaks:

## Input[edit]

1 6 4 2 1 3 1 4 4 1 2

## Output[edit]

42