codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1648A.md (1947B)


      1 Source: https://codeforces.com/problemset/problem/1648/A
      2 
      3 A. Weird Sum
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Egor has a table of size $n \times m$, with lines numbered from $1$ to $n$ and columns numbered from $1$ to $m$. Each cell has a color that can be presented as an integer from $1$ to $10^5$.
     22 
     23 Let us denote the cell that lies in the intersection of the $r$-th row and the $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 a shortest path between them where each consecutive cells in the path must have a common side. The path can go through cells of any color. For example, in the table $3 \times 4$ 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)$.
     24 
     25 Egor decided to calculate the sum of manhattan distances between each pair of cells of the same color. Help him to calculate this sum.
     26 
     27 Input
     28 
     29 The first line contains two integers $n$ and $m$ ($1 \leq n \le m$, $n \cdot m \leq 100\,000$) — number of rows and columns in the table.
     30 
     31 Each of next $n$ lines describes a row of the table. The $i$-th line contains $m$ integers $c_{i1}, c_{i2}, \ldots, c_{im}$ ($1 \le c_{ij} \le 100\,000$) — colors of cells in the $i$-th row.
     32 
     33 Output
     34 
     35 Print one integer — the the sum of manhattan distances between each pair of cells of the same color.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 2 3
     43 1 2 3
     44 3 2 1
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 7
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 3 4
     57 1 1 2 2
     58 2 1 1 2
     59 2 2 1 1
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 76
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 4 4
     72 1 1 2 3
     73 2 1 1 2
     74 3 1 2 1
     75 1 1 2 1
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 129
     82 ```
     83 
     84 Note
     85 
     86 In the first sample there are three pairs of cells of same color: in cells $(1, 1)$ and $(2, 3)$, in cells $(1, 2)$ and $(2, 2)$, in cells $(1, 3)$ and $(2, 1)$. The manhattan distances between them are $3$, $1$ and $3$, the sum is $7$.