Cod sursa(job #833566)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 12 decembrie 2012 18:57:10
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <stack>
#include <cstring>

#define MAX 215


using namespace std;

char sir[MAX];
int V[MAX][MAX], Up[MAX][MAX], Down[MAX][MAX], Right[MAX], Left[MAX];
int aux[MAX][MAX], dpUp[MAX], dpDown[MAX];
int N, M, rez;

void CheckSides(int V[MAX][MAX], int L[MAX], int R[MAX], int line)
{
    stack<int> stk;
    for(int i = 1; i <= M; i++)
    {
        while(!stk.empty() && V[line][stk.top()] > V[line][i]) R[stk.top()] = i - 1, stk.pop();
        if(stk.empty()) L[i] = 1;
        else L[i] = stk.top() + 1;
        stk.push(i);
    }
    while(!stk.empty()) R[stk.top()] = M, stk.pop();
}

void solve()
{
    memset(dpUp, 0, sizeof(dpUp));
    memset(dpDown, 0, sizeof(dpDown));
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(!V[i][j]) Up[i][j] = Up[i - 1][j] + 1;
            else Up[i][j] = 0;
    for(int i = N; i; i--)
        for(int j = 1; j <= M; j++)
            if(!V[i][j]) Down[i][j] = Down[i + 1][j] + 1;
            else Down[i][j] = 0;
    for(int i = 1; i <= N; i++)
    {
        CheckSides(Up, Left, Right, i);
        int part = 0;
        for(int j = 1; j <= M; j++) part = max(part, Up[i][j] * (Right[j] - Left[j] + 1));
        dpUp[i] = max(dpUp[i - 1], part);
    }
    for(int i = N; i; i--)
    {
        CheckSides(Down, Left, Right, i);
        int part = 0;
        for(int j = 1; j <= M; j++) part = max(part, Down[i][j] * (Right[j] - Left[j] + 1));
        dpDown[i] = max(dpDown[i + 1], part);
    }
    for(int i = 1; i < N; i++) rez = max(rez, dpUp[i] + dpDown[i + 1]);
}

int main()
{
    ifstream in("bmatrix.in");
    in>>N>>M; in.get();
    for(int i = 1; i <= N; i++)
    {
        in.getline(sir, MAX);
        for(int j = 1; j <= M; j++) V[i][j] = sir[j - 1] - '0';
    } in.close();
    solve();
    memcpy(aux, V, sizeof(aux));
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            V[j][i] = aux[i][j];
    swap(N, M);
    ofstream out("bmatrix.out"); out<<rez; out.close();
    return 0;
}