Editorial for DMOPC '21 Contest 2 P4 - Water Mechanics

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.

Author: Riolku

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: