Rezolvare PBinfo #4399

Cerința

Se dă o matrice binară de dimensiuni \(n\times m\). Determinați numărul de cvadruplete \((r_1,r_2,c_1,c_2)\) care respectă următoarele condiții:

• \(1\le r_1 < r_2\le N\) și \(1\le c_1 < c_2\le M\).
• Celulele \((r_1,c_1)\) și \((r_1,c_2)\) conțin valoarea \(1\).
• Celulele \((r_2,c_1)\), \((r_2,c_1+1)\), …, \((r_2,c_2)\) conțin toate valoarea \(1\).

Date de intrare

Pe prima linie se vor afla valorile \(n\) și \(m\) (dimensiunile tablei). Următoarele \(n\) linii descriu matricea. Fiecare va conține \(m\) valori de \(0\) sau \(1\). A \(c\)-a valoare de pe a \(r\)-a dintre aceste linii reprezintă celula \((r,c)\).

Date de ieșire

Pe prima linie se va afișa numărul de cvadruplete care respectă condițiile.

Restricții și precizări

• Pentru toate testele, se respectă \(1 \le n\cdot m \le 10^5\).
• Subtask 1, 20p: \(n,m \le 40\)
• Subtask 2, 30p: \(n,m \le 100\)
• Subtask 3, 20p: \(n,m \le 300\)
• Subtask 4, 30p: restricțiile inițiale

Exemplu 1:

Intrare

3 3
1 0 1
0 0 0
1 1 1

Ieșire

1

Explicație

Singurul cvadruplet este format din \(r_1=1\), \(r_2=3\), \(c_1=1\) și \(c_2=3\). Celulele \((1,1)\), \((1,3)\), \((3,1)\), \((3,2)\) și \((3,3)\) conțin toate valoarea \(1\), deci condiția este respectată.

Exemplu 2:

Intrare

3 4
1 0 1 1
1 1 1 0
1 1 1 1

Ieșire

7

Explicație

Celulele de valoare \(1\) din cele \(7\) cvadruplete sunt reprezentate mai jos: