Cod sursa(job #1988121)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 2 iunie 2017 09:29:26
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

const int nMax = 205;
const int mMax = 205;

int n, m;
char a[nMax][mMax];
int rasp = 0;

void citire()
{
    ifstream in("bmatrix.in");
    in >> n >> m;
    for(int i = 1; i <= n; ++i)
        in >> (a[i] + 1);
    in.close();
}

int GetMax(int startX, int startY, int stopX, int stopY)
{
    int ret = 0;
    static int height[mMax];
    static int firstSmallerSt[mMax];
    static int firstSmallerDr[mMax];
    stack<int> st;
    for(int i = startY; i <= stopY; ++i)
        height[i] = 0;
    height[startY - 1] = height[stopY + 1] = -1;
    int length;
    for(int i = startX; i <= stopX; ++i) //fixam linia de jos
    {
        for(int j = startY; j <= stopY; ++j)
        {
            if(a[i][j] == '0')
                height[j]++;
            else
                height[j] = 0;
        }
        st.push(startY - 1);
        for(int j = startY; j <= stopY; ++j)
        {
            while(st.empty() == false && height[j] <= height[st.top()])
                st.pop();
            firstSmallerSt[j] = st.top();
            st.push(j);
        }
        while(st.empty() == false)
            st.pop();
        st.push(stopY + 1);
        for(int j = stopY; j >= startY; --j)
        {
            while(st.empty() == false && height[j] <= height[st.top()])
                st.pop();
            firstSmallerDr[j] = st.top();
            st.push(j);
        }
        while(st.empty() == false)
            st.pop();
        for(int j = startY; j <= stopY; ++j)
        {
            if(height[j] == 0)
                continue;
            length = firstSmallerDr[j] - firstSmallerSt[j] - 1;
            ret = max(ret, length * height[j]);
        }
    }
    return ret;
}

void rezolvare()
{
    for(int i = 1; i < n; ++i)
        rasp = max(rasp, GetMax(1, 1, i, m) + GetMax(i+1, 1, n, m));
    for(int i = 1; i < m; ++i)
        rasp = max(rasp, GetMax(1, 1, n, i) + GetMax(1, i+1, n, m));
}

void afisare()
{
    ofstream out("bmatrix.out");
    out << rasp;
    out.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}