Cod sursa(job #1184085)

Utilizator apopeid15Apopei Daniel apopeid15 Data 11 mai 2014 10:53:58
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<cstdio>
#include<iostream>
using namespace std;
#define NMAX 205
int h[NMAX][NMAX] , st[NMAX][NMAX] , dr[NMAX][NMAX] , dq[NMAX];
int N , M , l , r , best ;
char s[NMAX][NMAX];
 
int solve1(int x1 , int x2 , int y1 , int y2)
{
    int ret = 0;
    for(int i = x1 ; i <= x2 ; ++i )
        for(int j = y1 ; j <= y2 ; ++j )
            ret = max(ret,h[i][j]*(min(dr[i][j],y2)-max(st[i][j],y1)+1));
    return ret;
}
 
int solve2(int x1 , int x2 , int y1 , int y2)
{
    int ret = 0;
    for(int i = x1 ; i <= x2 ; ++i )
        for(int j = y1 ; j <= y2 ; ++j )
            ret = max(ret,min(h[i][j],i-x1+1)*(dr[i][j]-st[i][j]+1));
    return ret;
}
 
void solve();
 
int main()
{
    freopen("bmatrix.in" , "r" , stdin );
    freopen("bmatrix.out" , "w" , stdout );
    scanf("%d%d" , &N , &M );
    for(int i = 1 ; i<= N ; ++i )
        scanf("%s" , s[i]+1);
    solve();
    printf("%d\n" , best);
    return 0;
}
 
void solve()
{
    for(int i = 1 ; i <= N ; ++i )
    {
        h[i][0] = h[i][M+1] = -1;
        for(int j  = 1 ; j <= M ; ++j )
            if(s[i][j] == '0')h[i][j] = h[i-1][j]+1;
            else h[i][j] = 0;
 
        dq[1] = 0;
        l = r = 1;
        for(int j = 1 ; j <= M ; ++j )
        {
            while(h[i][j] <= h[i][dq[r]])r--;
            dq[++r] = j;
            st[i][j] = dq[r-1]+1;
        }
        dq[1] = M+1;
        l = r = 1;
        for(int j = M ; j ; j--)
        {
            while(h[i][j] <= h[i][dq[r]])r--;
            dq[++r] = j;
            dr[i][j] = dq[r-1]-1;
        }
    }
 
    for(int i = 1 ; i < M ; ++i )
        best = max(best,solve1(1,N,1,i) + solve1(1,N,i+1,M));
    for(int i = 1 ; i < N ; ++i )
        best = max(best,solve2(1,i,1,M) + solve2(i+1,N,1,M));
}