Cod sursa(job #1812906)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 22 noiembrie 2016 15:49:44
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <algorithm>
#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 dr[maxn][maxn], st[maxn][maxn];
int aux[maxn][maxn], sus[maxn][maxn];
int dp1[maxn], dp2[maxn], dp3[maxn], dp4[maxn];
stack <int> stst;
stack <int> stdr;
char T[maxn];

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

void rot(int n, int m)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            aux[j][n - i + 1] = M[i][j];
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            M[i][j] = aux[i][j];
}

void solve(int dp[], int n, int m)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(M[i][j] == 1)
                sus[i][j] = 0;
            else
                sus[i][j] = sus[i - 1][j] + 1;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        erase_st();
        for(int j = 1; j <= m; 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] = 0;
            stst.push(j);
        }
        //stdr.push(y2 + 1);
        for(int j = m; j >= 1; 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] = m + 1;
            stdr.push(j);
        }
        for(int j = 1; j <= m; j++)
            dp[i] = max(dp[i], sus[i][j] * (dr[i][j] - st[i][j] - 1));
    }
}

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';
    }
    solve(dp1, n, m);
    rot(n, m);
    solve(dp3, m, n);
    rot(m, n);
    solve(dp2, n, m);
    rot(n, m);
    solve(dp4, m, n);
    int mx = 0;
    reverse(dp2 + 1, dp2 + n + 1);
    reverse(dp4 + 1, dp4 + m + 1);
    for(int i = 1; i < n; i++)
        mx = max(mx, dp1[i] + dp2[i + 1]);
    //for(int i = 1; i <= n; i++)
        //cerr << dp2[i] << " ";
    for(int i = 1; i < m; i++)
        mx = max(mx, dp3[i] + dp4[i + 1]);
    out << mx << "\n";
    return 0;
}