| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 27 | 19 | 17 | 70.833% |
Egor has table of size $n \times m$, where all lines are numbered from $1$ to $n$ and all columns are numbered from $1$ to $m$. Each cell is painted in some color that can be presented as integer from $1$ to $10^9$.
Let us call the cell that lies in $r$-th row and $c$-th column as $(r, c)$. We define the manhattan distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ as the length of shortest path between them where each consecutive cells have common side. The path can go through cells of any color. For example, the manhattan distance between $(1, 2)$ and $(3, 3)$ is 3, one of the shortest paths is the following: $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$.
Egor decided to calculate the sum of manhattan distances between each pair of cells of same color. Help him to calculate this sum.
The first line contains two integers $n$ and $m$ ($1 \leq n \le m$, $n \cdot m \leq 500\,000$) --- number of rows and columns in the table.
Each of next $n$ lines describes the rows of the table. $i$-th line contains $m$ integers $c_{i1}, c_{i2}, \ldots, c_{im}$ ($1 \le c_{ij} \le 10^9$) --- colors of cells in $i$-th row.
Print one integer --- the the sum of manhattan distances between each pair of cells of same color.
We define $C$ as the maximum number of color in the table.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 23 | $n \cdot m \le 1000$ |
| 2 | 17 | $n=1$ |
| 3 | 15 | $n=2$ |
| 4 | 20 | $C \le 2$ |
| 5 | 25 |
2 3 1 2 3 3 2 1
7
3 4 1 1 2 2 2 1 1 2 2 2 1 1
76
4 4 1 1 2 3 2 1 1 2 3 1 2 1 1 1 2 1
129
In the first sample there are three pairs of cells of same color: in coordinates $(1, 1)$ and $(2, 3)$, in coordinates $(1, 2)$ and $(2, 2)$, in coordinates $(1, 3)$ and $(2, 1)$. The manhattan distances between them are $3$, $1$ and $3$, the sum is $7$.
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2021-22 > Day 1 C번