## Editorial for Art Academy V: Ruin

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

For this problem, let's define the terms "active" and "resting". The active person is the one who caught the most recent painting, and the resting person is the one who did not. For convenience, let us also define a function , which returns the Manhattan distance between the th and th painting. At the th painting, we know that the active person caught the th painting (by definition). Therefore, the only variables are the position of the current painting and the position of the resting person. We can now use dynamic programming to solve this problem. The state is , which represents the minimum cost to catch the first paintings where the resting person most recently caught the th painting. For each , there are two transitions:

The active person catches the current painting. This gives .

The resting person catches the current painting (and becomes the active person), and the active person becomes the resting person. This gives the transition since we know that the active person, who is now resting, last caught the th painting.

Our final answer is .

Note that whether

or his aide is active does not matter except for the first time they catch a painting, since that is the only time their position differs (at the same index). This can be handled in multiple ways, and will be left as an exercise to the reader to test if they understand the solution.**Time Complexity:**

## Comments