Cod sursa(job #1811236)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 20 noiembrie 2016 22:57:17
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <stack>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int maxn = 205;
bitset <maxn> M[maxn];
int sus[maxn][maxn];
int st[maxn][maxn];
int dr[maxn][maxn];
stack <int> stst;
stack <int> stdr;
char T[maxn];

void erase_st()
{
    while(!stst.empty())
        stst.pop();
    while(!stdr.empty())
        stdr.pop();
}

void erase_mat(int x1, int x2, int y1, int y2)
{
    for(int i = x1 - 1; i <= x2 + 1; i++)
    {
        for(int j = y1 - 1; j <= y2 + 1; j++)
        {
            st[i][j] = 0;
            dr[i][j] = 0;
            sus[i][j] = 0;
        }
    }
}

int solve(int x1, int y1, int x2, int y2)
{
    erase_mat(x1, x2, y1, y2);
    for(int i = x1; i <= x2; i++)
    {
        for(int j = y1; j <= y2; j++)
        {
            if(M[i][j] == 1)
                sus[i][j] = 0;
            else
                sus[i][j] = sus[i - 1][j] + 1;
        }
    }
    for(int i = x1; i <= x2; i++)
    {
        erase_st();
        for(int j = y1; j <= y2; j++)
        {
            while(!stst.empty() && sus[i][stst.top()] >= sus[i][j])
                stst.pop();
            if(!stst.empty())
                st[i][j] = stst.top();
            else
                st[i][j] = y1 - 1;
            stst.push(j);
        }
        //stdr.push(y2 + 1);
        for(int j = y2; j >= y1; j--)
        {
            while(!stdr.empty() && sus[i][stdr.top()] >= sus[i][j])
                stdr.pop();
            if(!stdr.empty())
                dr[i][j] = stdr.top();
            else
                dr[i][j] = y2 + 1;
            stdr.push(j);
        }
    }
    int mx = 0;
    for(int i = x1; i <= x2; i++)
        for(int j = y1; j <= y2; j++)
            mx = max(mx, sus[i][j] * (dr[i][j] - st[i][j] - 1));
    return mx;
}

int main()
{
    int n, m;
    in >> n >> m;
    in.getline(T, maxn);
    for(int i = 1; i <= n; i++)
    {
        in.getline(T, maxn);
        for(int j = 0; j < m; j++)
            M[i][j + 1] = T[j] - '0';
    }
    int mx = 0;
    for(int lin = 1; lin < n; lin++)
        mx = max(mx, solve(1, 1, lin, m) + solve(lin + 1, 1, n, m));
    for(int col = 1; col < m; col++)
        mx = max(mx, solve(1, 1, n, col) + solve(1, col + 1, n, m));
    out << mx << "\n";
    return 0;
}