Cod sursa(job #1988671)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 4 iunie 2017 10:05:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

const int nMax = 205;
const int mMax = 205;
const int UP = 0;
const int LEFT = 1;
const int DOWN = 2;
const int RIGHT = 3;

int n, m;
char a[nMax][mMax];
char t[nMax][mMax];
int maxMatrix[4][nMax];
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();
}

void GetMax(int ret[])
{
    static int height[mMax];
    static int firstSmallerSt[mMax];
    static int firstSmallerDr[mMax];
    stack<int> st;
    for(int i = 1; i <= m; ++i)
        height[i] = 0;
    height[0] = height[m + 1] = -1;
    int length;
    for(int i = 1; i <= n; ++i) //fixam linia de jos
    {
        for(int j = 1; j <= m; ++j)
        {
            if(a[i][j] == '0')
                height[j]++;
            else
                height[j] = 0;
        }
        st.push(1 - 1);
        for(int j = 1; j <= m; ++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(m + 1);
        for(int j = m; j >= 1; --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 = 1; j <= m; ++j)
        {
            if(height[j] == 0)
                continue;
            length = firstSmallerDr[j] - firstSmallerSt[j] - 1;
            ret[i] = max(ret[i], length * height[j]);
        }
    }
}

void RotateMatrix()
{
    swap(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            t[i][j] = a[j][n - i + 1];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            a[i][j] = t[i][j];
}

void rezolvare()
{
    for(int i = 0; i < 4; ++i)
    {
        GetMax(maxMatrix[i]);
        RotateMatrix();
    }
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
            rasp = max(rasp, maxMatrix[UP][i] + maxMatrix[DOWN][n - j + 1]);
    for(int i = 1; i < m; ++i)
        for(int j = i + 1; j <= m; ++j)
            rasp = max(rasp, maxMatrix[LEFT][i] + maxMatrix[RIGHT][m - j + 1]);
}

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

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