# PBinfo #4399 – Fetze – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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:

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	int mat[N + 2][M + 2];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> mat[i][j];
		}
	}
	ll answer = 0;
	if (N <= M) {
		for (int i1 = 1; i1 <= N; i1++) {
			for (int i2 = i1 + 1; i2 <= N; i2++) {
				int cnt = 0;
				for (int j = 1; j <= M; j++) {
					if (mat[i2][j] == 0) {
						cnt = 0;
					} else if (mat[i1][j] == 1) {
						answer += cnt;
						cnt++;
					}
				}
			}
		}
	} else {
		bool ok[N + 2];
		for (int j1 = 1; j1 <= M; j1++) {
			for (int i = 1; i <= N; i++) {
				ok[i] = mat[i][j1];
			}
			for (int j2 = j1 + 1; j2 <= M; j2++) {
				int cnt = 0;
				for (int i = 1; i <= N; i++) {
					if (mat[i][j2] == false) {
						ok[i] = false;
					}
					if (ok[i] == true) {
						answer += cnt;
					}
					if (mat[i][j1] == true && mat[i][j2] == true) {
						cnt++;
					}
				}
			}
		}
	}
	cout << answer << "\n";
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4399)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4399/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4399/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)