P6537 [COCI 2013/2014 #1] RATAR

Given an $n \times n$ matrix, determine how many pairs of submatrices have exactly one common vertex and have equal element sums. Note that the **common vertex** here means that the two submatrices **touch at a corner**, not that they **share a common cell**. Please refer to Sample 1 to understand the meaning of a **common vertex**.

The first line contains a positive integer $n$. The next $n$ lines each contain $n$ integers, denoted as $a_{i,j}$, and **they may be negative**.

Output a single line containing the number of valid pairs.

#### Constraints - For $40\%$ of the testdata, $1 \le n \le 10$. - For $100\%$ of the testdata, $1 \le n \le 50$, $-1000 \le a_{i,j} \le 1000$. #### Sample 1 Explanation The possible rectangle pairs are: $(0,0)-(1,1)$ and $(2,2)-(2,2)$; $(1,0)-(1,0)$ and $(0,1)-(0,1)$; $(2,0)-(2,0)$ and $(1,1)-(1,1)$; $(1,1)-(1,1)$ and $(0,2)-(0,2)$; $(2,1)-(2,1)$ and $(1,2)-(1,2)$; $(2,0)-(2,1)$ and $(0,2)-(1,2)$; $(1,0)-(2,0)$ and $(0,1)-(0,2)$. In total there are $7$ **pairs**, so the output is $7$. #### Note **Translated from [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf) _T3 RATAR_.** ------------ $\mathtt{Subtask \ 0}$ is the sample testdata. (10 pts) In $\mathtt{Subtask \ 1}$, all testdata satisfy $1 \le n \le 10$. (30 pts) In $\mathtt{Subtask \ 2}$, all testdata satisfy $1 \le n \le 50$, $-1000 \le a_{i,j} \le 1000$. **Please note the time limit for this subtask.** (60 pts) Translated by ChatGPT 5