## Editorial for IOI '15 P4 - Horses

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To solve the first subtask, we need to just calculate our answer using dynamic programming.

- what is the maximal profit if we pass days and we have horses, then we got horses and check all number of horses that we sell today and go to the next day.

#### Observation 1

First of all, let's consider two points and . What if we sell horses in the and day? And check which day is more profitable.

Profit of day:

Profit of day:

It depends on this:

• if it's then it's more profitable to sell horses in day
• if it's then it's more profitable to sell horses in day
• if it's then it doesn't matter if we sell them in day or in day

From this point, it's clear that it is better to sell all our horses in one day that gives us maximal profit.

Using this observation, we can solve 2 subtasks.

After each query, we can solve the problem in .

#### Observation 2

If all , then after days, , so position less than or equal can never be an optimal solution, because even if and , .

It's enough to check only the last positions.

#### Observation 3

The main problem in the last subtask is , but in that case, multiplication first numbers and is not changed. This allows us to merge consecutive positions with . When we merge this position, we should take the maximal . So if we do that, it's enough to check the last positions, because there can be no more than merged 's between last positions where .

So we can store our state in some structure like set, that provides us information about current merged positions, and some structure that provides us RMQ. So solution per query will be . Then to calculate the answer, we can use something like segment tree.

So overall complexity will be .