piscina

O piscină dreptunghiulară de $N$ metri lungime pe $M$ metri lățime este împărțită în $N \times M$ zone de $1 m^2$. O astfel de zonă are aceeași adâncime pe toată suprafața ei de $1 m^2$, dar două zone diferite pot avea adâncimi diferite. Adâncimile zonelor, exprimate în metri ($m$), sunt numere naturale nenule și sunt salvate într-o matrice $A$ cu $N$ linii și $M$ coloane.

Din cauza restricțiilor constructive ale piscinei, matricea $A$ trebuie să fie bine definită, în sensul în care pentru toate submatricele de dimensiune $2 \times 2$ formate din linii consecutive și coloane consecutive ale matricei $A$, numerele aflate pe oricare dintre cele două diagonale nu sunt amândouă mai mici decât fiecare dintre celelalte două elemente. În conformitate cu legile fizicii, dacă o zonă din piscină conține apă, apa tinde să se distribuie în zonele adiacente pe verticală și orizontală care au adâncimea sub nivelul apei.

Proprietarul vrea să economisească apă. Ținând cont de cererea din partea publicului, nu are nevoie să umple neapărat toată piscina, ci cel puțin o suprafață dreptunghiulară cu $K$ zone în lungime și $K$ zone în lățime, unde $K \leq N$ și $K \leq M$. Suprafața umplută cu apă poate fi situată oriunde în piscină. Adâncimea apei pe suprafața umplută trebuie să fie de cel puțin $1 m$ în fiecare punct. Proprietarul vrea să afle $X$, cantitatea minimă de apă necesară în acest scop.

De exemplu, pentru piscina reprezentată în matricea $A$ de mai jos și $K = 2$, sunt necesari $X = 6 m^3$ de apă, iar suprafața acoperită este dată de cele $5$ zone a căror adâncime este scrisă colorat.
$A = \begin{bmatrix} 1 & \textcolor{red}{\textbf 2} & \textcolor{red}{\textbf 3} & 1 \\ 1 & \textcolor{red}{\textbf 2} & \textcolor{red}{\textbf 2} & 1 \\ 1 & \textcolor{red}{\textbf 2} & 1 & 1 \\ \end{bmatrix}$

Cerință

Scrieți în $\text{C}$ sau în $\text{C++}$:

1. o funcție verifica, cu parametrii $A$, $N$, $M$, care determină dacă $A$ este bine definită în sensul de mai sus (funcția întoarce $0$ sau $1$; presupuneți că $A$ conține doar numere naturale nenule);
2. o funcție complet, cu parametrii $A$, $N$, $M$, care întoarce cantitatea de apă necesară pentru a umple toată piscina cu apă de adâncime cel puțin $1 m$ (nu validați datele de intrare);
3. o funcție optim, cu parametrii $A$, $N$, $M$ și $K$, care întoarce $X$, cantitatea minimă de apă necesară (nu validați datele de intrare).

Antetele funcțiilor descrise mai sus sunt acestea:

bool verifica(int A[101][101], int N, int M);
int complet(int A[101][101], int N, int M);
int optim(int A[101][101], int N, int M, int K);

Restricții și precizări

• $1 \leq N, M \leq 100$
• Este garantat că suma elementelor matricei $A$ este $\leq 10^9$.
• Matricea $A$ este indexată de la $1$.
• Distribuția punctajelor în ordinea cerințelor este $25,25,50$. În concurs a fost $5,5,10$.
• Atenție! Cerința este să implementați cele 3 funcții descrise în enunț. Sursa pe care o veți trimite nu va conține funcția main! Iată un exemplu de sursă validă:

#include <algorithm>
using namespace std;

bool verifica(int A[101][101], int N, int M) {
    return 0;
}

int complet(int A[101][101], int N, int M) {
    return A[1][1];
}

int optim(int A[101][101], int N, int M, int K) {
    return *max_element(A[1] + 1, A[1] + M+1);
}