Cod sursa(job #2065379)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 13 noiembrie 2017 18:54:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <deque>
#define DIM 202

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

int n, m, frecv[DIM], a[DIM][DIM], isus[DIM], ijos[DIM], last[DIM], first[DIM], jsus[DIM], jjos[DIM];

deque<int> c;

void drmax(int i, int tip){
    int ariemax = 0;
    c.clear();
    c.push_back(0);
    int cnt = 0;
    if(tip <= 2)
        cnt = m;
    else
        cnt = n;
    for(int j = 1; j <= cnt + 1; ++ j){
        while(!c.empty() && frecv[c.back()] >= frecv[j]){
            last[c.back()] = j - 1;
            c.pop_back();
        }
        if(frecv[j])
            first[j] = c[c.size() - 1] + 1;
        c.push_back(j);
    }
    for(int j = 1; j <= cnt; ++ j)
        ariemax = max(ariemax, (last[j] - first[j] + 1) * frecv[j]);
    if(tip == 1)
        isus[i] = max(isus[i - 1], ariemax);
    if(tip == 2)
        ijos[i] = max(ijos[i + 1], ariemax);
    if(tip == 3)
        jsus[i] = max(jsus[i - 1], ariemax);
    if(tip == 4)
        jjos[i] = max(jjos[i + 1], ariemax);
}

void resetfrecv(){
    for(int i = 1; i <= m; ++ i)
        frecv[i] = 0;
}

int main()
{
    f>>n>>m;
    char ch;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j){
            f>>ch;
            a[i][j] = ch - '0';
        }

    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j)
            if(a[i][j])
                frecv[j] = 0;
            else
                ++ frecv[j];
        drmax(i, 1);
    }

    resetfrecv();

    for(int i = n; i >= 1; -- i){
        for(int j = 1; j <= m; ++ j)
            if(a[i][j])
                frecv[j] = 0;
            else
                ++ frecv[j];
        drmax(i, 2);
    }

    int Aria = -1;

    for(int i = 1; i < n; ++ i)
        Aria = max(Aria, isus[i] + ijos[i + 1]);

    resetfrecv();

    for(int i = 1; i <= m; ++ i){
        for(int j = 1; j <= n; ++ j)
            if(a[j][i])
                frecv[j] = 0;
            else
                ++ frecv[j];
        drmax(i, 3);
    }

    resetfrecv();

    for(int i = m; i >= 1; -- i){
        for(int j = 1; j <= n; ++ j)
            if(a[j][i])
                frecv[j] = 0;
            else
                ++ frecv[j];
        drmax(i, 4);
    }

    for(int i = 1; i < m; ++ i)
        Aria = max(Aria, jsus[i] + jjos[i + 1]);

    g<<Aria<<'\n';

    return 0;
}