Matrius de Monge P16242

Una matriu $n \times m$ es diu que és una matriu de Monge (en honor al matemàtic francès Gaspard Monge) si, per a tots els $i, j, k, \ell$ tals que $0 \le i < k < n$ i $0 \le j < \ell < m$, es compleix $$A[i][j] + A[k][\ell] \le A[i][\ell] + A[k][j].$$

Per exemple, aquesta matriu és de Monge: $$\begin{pmatrix} 10 & 17 & 13 & 28 & 23 \\ 17 & 22 & 16 & 29 & 23 \\ 24 & 28 & 22 & 34 & 24 \\ 11 & 13 & 6 & 17 & 7 \\ \end{pmatrix}$$ Si prenem la intersecció de les files 1 i 3 amb les columnes 0 i 4, els quatre elements són: $$\begin{pmatrix} 17 & 23 \\ 11 & 7 \\ \end{pmatrix}$$ Fixem-nos que $17 + 7 \le 11 + 23$. Aquesta propietat es compleix a tot arreu de la matriu.

Feu una funció

bool es_Monge(const vector<vector<int>>& M);

tal que, donada una matriu $M$ de mides $n \times m$, amb $n \ge 2$ i $m \ge 2$, retorni cert si i només si $M$ és de Monge.

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

El jutge acceptarà solucions amb cost $\Theta(n^2 \cdot m^2)$, però no són eficients i això es penalitzarà a la correcció manual.