Cod sursa(job #2968514)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 21 ianuarie 2023 13:35:09
Problema BMatrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

const int NMAX = 202;
int h[NMAX],s[NMAX];
int m,n,sz,rasp;
bool v[NMAX][NMAX];
string str;
int raspSus[NMAX];
int raspJos[NMAX];
int raspSt[NMAX];
int raspDr[NMAX];

void calcLin(int i, bool sus)
{
    for(int j=1; j<=m; j++)
    {
        if(v[i][j]) h[j] = 0;
        else h[j]++;
    }
    sz = rasp = 0;
    for(int j=1; j<=m; j++)
    {
        for(; sz>0 && h[s[sz]] >= h[j]; sz--)
            rasp = max(rasp, h[s[sz]] * (j - s[sz-1] - 1));
        s[++sz] = j;
    }
    for(; sz>=0; sz--)
        rasp = max(rasp, h[s[sz]] * (m - s[sz-1]));
    if(sus) raspSus[i] = rasp;
    else raspJos[i] = rasp;
}

void calcCol(int j, bool st)
{
    for(int i=1; i<=n; i++)
    {
        if(v[i][j]) h[i] = 0;
        else h[i]++;
    }
    sz = rasp = 0;
    for(int i=1; i<=n; i++)
    {
        for(; sz>0 && h[s[sz]] >= h[j]; sz--)
            rasp = max(rasp, h[s[sz]] * (i - s[sz-1] - 1));
        s[++sz] = i;
    }
    for(; sz>=0; sz--)
        rasp = max(rasp, h[s[sz]] * (n - s[sz-1]));
    if(st) raspSt[j] = rasp;
    else raspDr[j] = rasp;
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        fin>>str;
        for(int j=1; j<=m; j++)
        {
            v[i][j] = (str[j-1] == '1');
        }
    }
    for(int i=1; i<=n; i++) calcLin(i,1);
    memset(h,0,sizeof h);
    for(int i=n; i>=1; i--) calcLin(i,0);
    memset(h,0,sizeof h);

    for(int j=1; j<=m; j++) calcCol(j,1);
    memset(h,0,sizeof h);
    for(int j=m; j>=1; j--) calcCol(j,0);
    memset(h,0,sizeof h);

    for(int i=2; i<=n; i++) raspSus[i] = max(raspSus[i], raspSus[i-1]);
    for(int i=n-1; i>=1; i--) raspJos[i] = max(raspJos[i], raspJos[i+1]);

    for(int j=2; j<=m; j++) raspSt[j] = max(raspSt[j], raspSt[j-1]);
    for(int j=m-1; j>=1; j--) raspDr[j] = max(raspDr[j], raspDr[j+1]);

    rasp=0;
    for(int i=1; i<n; i++)
    {
        rasp = max(rasp, raspSus[i] + raspJos[i+1]);
    }
    for(int j=1; j<m; j++)
    {
        rasp = max(rasp, raspSt[j] + raspDr[j+1]);
    }
    fout<<rasp;
    return 0;
}