## Editorial for COCI '09 Contest 7 #5 Kraljevi

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 start, note that simply calculating all pairs of distances is time complexity and scores of points.

For of points, we use dynamic programming in time complexity. First, we find the sum of distances between all kings with coordinates and , and on the second pass with and . To find the sum, we start at and work left to right / top to bottom. We need the following:

`row_count(X, Y), row_sum(X, Y)`

- number of pieces in the fields with coordinates , and the sum of distances to the field .`col_count(X, Y), col_sum(X, Y)`

- same as row but for columns`dp_count(X, Y), dp_sum(X, Y)`

- same but for the lower left part of the board, in other words for fields and .

For dynamic programming, we need the following relations:

```
row_sum(X, Y) = row_sum(X, Y-1) + row_count(X, Y-1)
row_count(X, Y) = row_count(X, Y-1) + B(X, Y)
col_sum(X, Y) = col_sum(X-1, Y) + col_count(X-1, Y)
col_count(X, Y) = col_count(X-1, Y) + B(X, Y)
dp_sum(X, Y) = dp_sum(X-1, Y-1) + dp_count(X-1, Y-1) + row_sum(X, Y) + col_sum(X, Y) + B(X, Y)
dp_count(X, Y) = dp_count(X-1, Y-1) + row_count(X, Y) + col_count(X, Y) + B(X, Y)
```

Where is if the field contains the figure of the current player, and otherwise.

Now we can easily see that the sum of field to other pieces is:

`sum(X, Y) = dp_sum(X-1, Y-1) + row_sum(X, Y) + col_sum(X, Y)`

## Comments

A simpler solution is to translate (x,y) -> (x+y,x-y) (or similar), so the problem becomes sum of Manhattan distances instead of Chebyshev. Then you can independently sum the contribution from x and y coordinates with sorting or brute force.