fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxN = 1e3 + 5;
  5. int n, m;
  6. int a[maxN][maxN];
  7. int histogram[maxN][maxN];
  8.  
  9. int get_left(int col, int row){
  10.     int height = histogram[row][col], left = col;
  11.     while (left >= 1 && histogram[row][left] >= height)
  12.         left--;
  13.     return left + 1;
  14. }
  15.  
  16. int get_right(int col, int row){
  17.     int right = col, height = histogram[row][col];
  18.     while (right <= m && histogram[row][right] >= height)
  19.         right++;
  20.     return right - 1;
  21. }
  22.  
  23. int get_max_row(int row){
  24.     int ans = 0;
  25.     for (int i = 1; i <= m; i++){
  26.         ans = max(ans, histogram[row][i] * (get_right(i, row) - get_left(i, row) + 1));
  27.     }
  28.     return ans;
  29. }
  30.  
  31. int main(){
  32.     cin >> n >> m;
  33.     for (int i = 1; i <= n; i++)
  34.         for (int j = 1; j <= m; j++) {
  35.             cin >> a[i][j];
  36.             if (a[i][j] == 0)
  37.                 histogram[i][j] = 0;
  38.             else
  39.                 histogram[i][j] = histogram[i-1][j] + 1;
  40.         }
  41.  
  42.     int ans = 0;
  43.     for (int row = 1; row <= n; row++)
  44.         ans = max(ans, get_max_row(row));
  45.     cout << ans << '\n';
  46.     return 0;
  47. }
  48.  
  49.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/1nBv9V
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!