piscina

Time limit: 3s Memory limit: 16MB Input: Output:

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

Din cauza restricțiilor constructive ale piscinei, matricea AA trebuie să fie bine definită, în sensul în care pentru toate submatricele de dimensiune 2×22 \times 2 formate din linii consecutive și coloane consecutive ale matricei AA, 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 KK zone în lungime și KK zone în lățime, unde KNK \leq N și KMK \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 1m1 m în fiecare punct. Proprietarul vrea să afle XX, cantitatea minimă de apă necesară în acest scop.

De exemplu, pentru piscina reprezentată în matricea AA de mai jos și K=2K = 2, sunt necesari X=6m3X = 6 m^3 de apă, iar suprafața acoperită este dată de cele 55 zone a căror adâncime este scrisă colorat.
A=[123112211211]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 C\text{C} sau în C++\text{C++}:

  1. o funcție verifica, cu parametrii AA, NN, MM, care determină dacă AA este bine definită în sensul de mai sus (funcția întoarce 00 sau 11; presupuneți că AA conține doar numere naturale nenule);
  2. o funcție complet, cu parametrii AA, NN, MM, care întoarce cantitatea de apă necesară pentru a umple toată piscina cu apă de adâncime cel puțin 1m1 m (nu validați datele de intrare);
  3. o funcție optim, cu parametrii AA, NN, MM și KK, care întoarce XX, 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

  • 1N,M1001 \leq N, M \leq 100
  • Este garantat că suma elementelor matricei AA este 109\leq 10^9.
  • Matricea AA este indexată de la 11.
  • Distribuția punctajelor în ordinea cerințelor este 25,25,5025,25,50. În concurs a fost 5,5,105,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);
}

Log in or sign up to be able to send submissions!