Question

C++
#1267
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≤103


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.

Answer 1

#include <bits/stdc++.h> using namespace std; int n,m,x,maxx; char v[10001]; int v1[10001]; int get(int vec[], int k){ stack<int> s; int maxa = 0, tp, awt, i = 0; while (i < k){ if (s.empty() || vec[s.top()] <= vec[i]) s.push(i++); else { tp = s.top(); s.pop(); awt = vec[tp] * (s.empty() ? i : i - s.top() - 1); if (maxa < awt) maxa = awt; } } while (!s.empty()){ tp = s.top(); s.pop(); awt = vec[tp] * (s.empty() ? i : i - s.top() - 1); if (maxa < awt) maxa = awt; } return maxa; } int main(){ ifstream in("plaja.in"); ofstream out("plaja.out"); in>>n>>m; for(int j = 0; j <= n; ++j){ in.getline(v, 10001); for(int i = 0; i < (int)strlen(v); ++i) { if((v[i] - '0') == 1) v1[i] = 0; else if((v[i] - '0') == 0) v1[i] += 1; } x = get(v1, m); if(x > maxx) maxx = x; } out<<maxx; return 0; }