Cod sursa(job #826193)

Utilizator visanrVisan Radu visanr Data 30 noiembrie 2012 13:46:23
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <tr1/unordered_map>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <ctime>
using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define leftSon (node << 1)
#define rightSon ((node << 1) + 1)
#define nmax 210

int Up[nmax][nmax], Down[nmax][nmax], Left[nmax], Right[nmax], N, M, mat[nmax][nmax], AnsUp[nmax], AnsDown[nmax];
stack<int> St;
int ans;
char S[1000];

void Go()
{
    int i, j;
    memset(Up, 0, sizeof(Up));
    memset(Down, 0, sizeof(Down));
    memset(AnsUp, 0, sizeof(AnsUp));
    memset(AnsDown, 0, sizeof(AnsDown));
    for(i = 1; i <= N; i++)
        for(j = 1; j <= M; j++)
            if(mat[i][j] == 0)
                Up[i][j] = Up[i - 1][j] + 1;
            else
                Up[i][j] = 0;
    for(i = N; i; i--)
        for(j = 1; j <= M; j++)
            if(mat[i][j] == 0)
                Down[i][j] = Down[i + 1][j] + 1;
            else
                Down[i][j] = 0;
    for(i = 1; i <= N; i++)
    {
        for(j = 1; j <= M; j++)
        {
            while(!St.empty() && Up[i][St.top()] >= Up[i][j]) Right[St.top()] = j - 1, St.pop();
            if(St.empty()) Left[j] = 1;
            else Left[j] = St.top() + 1;
            St.push(j);
        }
        while(!St.empty()) Right[St.top()] = M, St.pop();
        int crt = 0;
        for(j = 1; j <= M; j++)
            crt = max(crt, Up[i][j] * (Right[j] - Left[j] + 1));
        AnsUp[i] = max(AnsUp[i - 1], crt);
        for(j = 1; j <= M; j++)
        {
            while(!St.empty() && Down[i][St.top()] >= Down[i][j]) Right[St.top()] = j - 1, St.pop();
            if(St.empty()) Left[j] = 1;
            else Left[j] = St.top() + 1;
            St.push(j);
        }
        while(!St.empty()) Right[St.top()] = M, St.pop();
        crt = 0;
        for(j = 1; j <= M; j++)
            crt = max(crt, Down[i][j] * (Right[j] - Left[j] + 1));
        AnsDown[i] = max(AnsDown[i + 1], crt);
    }
    for(i = 1; i < N; i++) ans = max(ans, AnsUp[i] + AnsDown[i + 1]);
}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    int i, j;
    scanf("%i %i\n", &N, &M);
    for(i = 1; i <= N; i++)
    {
        gets(S);
        for(j = 0; j < M; j++) mat[i][j + 1] = S[j] - '0';
    }
    Go();
    int aux[nmax][nmax];
    memcpy(aux, mat, sizeof(aux));
    for(i = 1; i <= N; i++)
        for(j = 1; j <= M; j++)
            mat[j][i] = aux[i][j];
    int auxx = N;
    N = M;
    M = auxx;
    Go();
    printf("%i\n", ans);
    return 0;
}