Advertisement
Alex_tz307

Dreptunghiul format doar din 0 de arie maxima

Feb 14th, 2021
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream fin("plaja.in");
  6. ofstream fout("plaja.out");
  7.  
  8. const int NMAX = 1001;
  9. int N, M, v[NMAX + 1], ans;
  10. string s;
  11.  
  12. void max_self(int &a, int b) {
  13.     a = max(a, b);
  14. }
  15.  
  16. void checkSol(int x1, int x2, int y) {
  17.     max_self(ans, (x2 - x1) * y);
  18. }
  19.  
  20. void solve() {
  21.     stack<int> S;
  22.     for(int i = 1; i <= M + 1; ++i) {
  23.         while(!S.empty() && v[S.top()] > v[i]) {
  24.             int index = S.top();
  25.             S.pop();
  26.             if(S.empty())
  27.                 checkSol(0, min(i, M), v[index]);
  28.             else
  29.                 checkSol(S.top(), i - 1, v[index]);
  30.         }
  31.         S.emplace(i);
  32.     }
  33. }
  34.  
  35. int main() {
  36.     fin >> N >> M;
  37.     for(int i = 0; i < N; ++i) {
  38.         fin >> s;
  39.         for(int j = 0; j < M; ++j)
  40.             if(s[j] == '0')
  41.                 ++v[j + 1];
  42.             else
  43.                 v[j + 1] = 0;
  44.         solve();
  45.     }
  46.     fout << ans << '\n';
  47. }
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement