Cod sursa(job #787046)

Utilizator S7012MYPetru Trimbitas S7012MY Data 12 septembrie 2012 15:42:41
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <stack>
#define DN 205
#define x first
#define y second
using namespace std;

typedef pair<int,int> per;

int n,m,h[DN],sol;
stack<per> s;
char mt[DN][DN];

int fa(int x1, int y1, int x2, int y2) {
    int ret=0;
    for(int i=y1-1; i<=y2+1; ++i) h[i]=0;
    for(int i=x1; i<=x2; ++i) {
        for(int j=y1; j<=y2; ++j) {
            if('0'==mt[i][j]) ++h[j];
            else h[j]=0;
        }
        s.push(make_pair(0,1));
        for(int j=y1; j<=y2+1; ++j) {
            ret=max(ret,h[j]);
            int lst=j;
            for(;s.size() && s.top().x>=h[j];s.pop()) {
                ret=max(ret,s.top().x*(j-s.top().y));
                lst=s.top().y;
            }
            s.push(make_pair(h[j],lst));
        }
    }
    for(;s.size();s.pop());
    return ret;
}

int main()
{
    ifstream f("bmatrix.in");
    ofstream g("bmatrix.out");
    f>>n>>m;
    for(int i=1; i<=n; ++i) f>>mt[i]+1;
    for(int i=1; i<=m/2; ++i) sol=max(sol,fa(1,1,n,i)+fa(1,i+1,n,m));
    for(int i=1; i<=n/2; ++i) sol=max(sol,fa(1,1,i,m)+fa(i+1,1,n,m));
    g<<sol;
    return 0;
}