Cod sursa(job #1823184)

Utilizator greenadexIulia Harasim greenadex Data 5 decembrie 2016 23:45:39
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <bits/stdc++.h>
 
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
  
using namespace std;
  
const string name = "bmatrix",
             in_file = name + ".in",
             out_file = name + ".out";
  
ifstream fin(in_file);
ofstream fout(out_file);
  
const int MAX = 201;
 
int n, m;
int matrix[MAX][MAX];
int heights[MAX][MAX];
vector<int> stackk;
int lefty[MAX], righty[MAX];
int dp[MAX][MAX];
 
void build_heights(int line) {
    memset(heights, 0, sizeof(heights));
    
    for (int i = line + 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (matrix[i][j]) {
                heights[i][j] = 0;
            } else {
                heights[i][j] = heights[i - 1][j] + 1;
            }
        }
    }

    for (int i = 1; i <= line; i++) {
         for (int j = 1; j <= m; j++) {
            if (matrix[i][j]) {
                heights[i][j] = 0;
            } else {
                heights[i][j] = heights[i - 1][j] + 1;
            }
        }
    }
}
 
int go(int x1, int y1, int x2, int y2) {
    int maxx = 0;
    for (int i = x1; i <= x2; i++) {
        stackk.clear();
        for (int j = y1; j <= y2; j++) {
            int height = heights[i][j];
             
            if (!height) {
                lefty[j] = 0;
                stackk.clear();
                continue;
            }
             
            while (!stackk.empty() && heights[i][stackk.back()] > height) {
                stackk.pop_back();
            }
 
            if (stackk.empty() || heights[i][stackk.back()] < height) {
                stackk.push_back(j);
                lefty[j] = j;
            } else {
                lefty[j] = stackk.back();
            }
        }
 
        stackk.clear();
        for (int j = y2; j > 0; j--) {
            int height = heights[i][j];
 
            if (!height) {
                righty[j] = 0;
                stackk.clear();
                continue;
            }
 
            while (!stackk.empty() && heights[i][stackk.back()] > height) {
                stackk.pop_back();
            }
 
            if (stackk.empty() || heights[i][stackk.back()] < height) {
                stackk.push_back(j);
                righty[j] = j;
            } else {
                righty[j] = stackk.back();
            }
 
        }
 
        for (int j = y1; j <= y2; j++) {
            dp[i][j] = heights[i][j] * (righty[j] - lefty[j] + 1);
            maxx = max(dp[i][j], maxx);
        }
    }
    return maxx;
}
 
int main() {
    fin >> n >> m;
     
    string str;
    for (int i = 1; i <= n; i++) {
        fin >> str;
        for (int j = 1; j <= m; j++) {
            matrix[i][j] = str[j - 1] - '0';
        }
    }
 
    int result = 0;
    for (int line = 1; line < n; line++) {
        build_heights(line);
        int topLeftSecond = line + 1, bottomRightFirst = line;
        result = max(result, go(1, 1, bottomRightFirst, m) + 
                                go (topLeftSecond, 1, n, m));
    }
    fout << result;
    return 0;
}