Cod sursa(job #1315284)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 12 ianuarie 2015 18:21:03
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <stack>
#define DIM 205

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int N,M,a[DIM][DIM],sol,sus[DIM],jos[DIM];
char s[DIM][DIM],b[DIM][DIM];
void afis(){
    for(int i=1;i<=N;i++)
        fout<<sus[i]<<" "<<jos[i]<<endl;
}
void solve_line1(int x){
    stack <pair <int ,int > > q;
    for(int i=1;i<=M+1;i++){
        if(q.empty() || a[x][i]>q.top().first)
            q.push(make_pair(a[x][i],1));
        else
            if(q.top().first==a[x][i])
                ++q.top().second;
        else{
            int nr=0,lg=0;
            while(!q.empty() && a[x][i]<q.top().first){
                nr=q.top().second;
                lg=q.top().first;
                q.pop();
                sus[x]=max(sus[x],nr*lg);
                //afis();
            }
            q.push(make_pair(a[x][i],nr+1));
        }
    }
}
void solve_line2(int x){
    stack <pair <int ,int > > q;
    for(int i=1;i<=M+1;i++){
        if(q.empty() || a[x][i]>q.top().first)
            q.push(make_pair(a[x][i],1));
        else
            if(q.top().first==a[x][i])
                ++q.top().second;
        else{
            int nr=0,lg=0;
            while(!q.empty() && a[x][i]<q.top().first){
                nr=q.top().second;
                lg=q.top().first;
                q.pop();
                jos[x]=max(jos[x],nr*lg);
                //afis();
            }
            q.push(make_pair(a[x][i],nr+1));
        }
    }
}
void rotate(){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            b[M-j+1][i]=s[i][j];
    swap(N,M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            s[i][j]=b[i][j];
}
void solve(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++)
            if(s[i][j]=='0')
                a[i][j]=a[i-1][j]+1;
            else
                a[i][j]=0;
        sus[i]=0;
        solve_line1(i);
    }
    for(int i=N;i>=1;i--){
        for(int j=M;j>=1;j--)
            if(s[i][j]=='0')
                a[i][j]=a[i+1][j]+1;
            else
                a[i][j]=0;
        jos[i]=0;
        solve_line2(i);
    }
    for(int i=2;i<=N;i++)
        sus[i]=max(sus[i],sus[i-1]);
    for(int i=N-1;i>=1;i--)
        jos[i]=max(jos[i],jos[i+1]);
    for(int i=1;i<N;i++)
        sol=max(sol,sus[i]+jos[i+1]);
}
int main(){
    fin>>N>>M;
    for(int i=1;i<=N;i++)
        fin>>s[i]+1;
    solve();
    rotate();
    solve();
    fout<<sol;
    fin.close();fout.close();
    return 0;
}