## Editorial for DMOPC '21 Contest 2 P4 - Water Mechanics

**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.**

Author:

#### Subtask 1

For this subtask, the simplest solution is probably, for all indices , determine, if water was poured here, the endpoints of the interval and . Now run a `dp[i]`

where `dp[i]`

represents the minimum cost such that the first cells have water in them. This should be a fairly classical DP: sort the intervals and transition in . Note that intervals can overlap.

**Time Complexity**:

#### Subtask 2

We can extend the previous solution. We need to calculate more efficiently. Walk through the indices and keep track of the running value. When you are on flat ground for too long, you should update this running value. Note that our values are the same, but done in reverse.

With these intervals, we can do two things. The first is to run a greedy solution where we take the interval with the farthest right point that still covers the leftmost uncovered cell, which works because the intervals are monotonically sorted by both and . The second is to miss this observation and throw a segment tree on top of our previous DP.

**Time Complexity**: or

## Comments