Cod sursa(job #1811150)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 20 noiembrie 2016 21:17:56
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream in("matrix2.in");
ofstream out("matrix2.out");
const int maxn = 1005;
int sus[maxn][maxn];
int M[maxn][maxn];
stack <int> stst;
stack <int> stdr;
int st[maxn][maxn];
int dr[maxn][maxn];
int n, m;

void prec()
{
    for(int i = 1; i <= n; i++)
    {
        while(!stst.empty())
            stst.pop();
        while(!stdr.empty())
            stdr.pop();
        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();
            stst.push(j);
        }
        stdr.push(m + 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();
            stdr.push(j);
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            in >> M[i][j];
            if(M[i][j] == 1)
                sus[i][j] = 0;
            else
                sus[i][j] = sus[i - 1][j] + 1;
        }
    }
    prec();
    int mx = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            mx = max(mx, sus[i][j] * (dr[i][j] - st[i][j] - 1));
    out << mx << "\n";
    /*
    for(int i = 1; i <= n; i++, cerr << "\n")
        for(int j = 1; j <= m; j++)
            cerr << st[i][j] << " ";
    */
    return 0;
}