Cerința
O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricii sunt codificate cu 0, însemnând o poziție liberă, și 1, însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.
Date de intrare
Fișierul de intrare plaja.in conține pe prima linie numerele n și m, iar pe următoarele n linii câte m caractere reprezentând plaja.
Date de ieșire
Fișierul de ieșire plaja.out va conține pe prima linie numărul S, reprezentând aria maximă a unui dreptunghi liber.
Restricții și precizări
1 ≤ n, m ≤ 1000
Exemplu
plaja.in
5 5 11111 11000 11100 11100 11110
plaja.out
6
Explicație
1 1 1 1 1
1 1 0 0 0
1 1 1 0 0
1 1 1 0 0
1 1 1 1 0
Suprafata dreptunghiulara de aria maxima este cea ingrosata.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema plaja:
#include <fstream>
#define MAX_N 1000
int hist[MAX_N + 1];
int st[MAX_N], s;
inline int MAX(const int &A, const int &B) {
return A > B ? A : B;
}
inline int solveHist(int n) {
int maxArea = 0;
s = 0;
hist[n] = 0;
for (int i = 0; i <= n; i++) {
while ((s > 0) && (hist[st[s - 1]] > hist[i])) {
s--;
maxArea = MAX(maxArea, hist[st[s]] * (!s ? i : i - 1 - st[s - 1]));
}
st[s++] = i;
}
return maxArea;
}
int main(void) {
int n, m;
int maxArea;
std::fstream f("plaja.in", std::ios::in);
f.tie(0);
std::ios_base::sync_with_stdio(0);
f >> n >> m;
maxArea = 0;
for (int i = 0; i < n; i++) {
f.get();
for (int j = 0; j < m; j++) {
if (f.get() == '0') {
hist[j]++;
} else {
hist[j] = 0;
}
}
maxArea = MAX(maxArea, solveHist(m));
}
f.close();
f.open("plaja.out", std::ios::out);
f << maxArea << '\n';
f.close();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1267 plaja
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1267 plaja de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!