Cod sursa(job #2340159)

Utilizator alexradu04Radu Alexandru alexradu04 Data 9 februarie 2019 20:53:00
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>

using namespace std;

ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");

const int N_MAX = 200;
const int M_MAX = 200;

int n, m;
int amax;
char c;

int h[1 + M_MAX];
pair < int, int > st[1 + M_MAX + 1];
int sol[4][1 + N_MAX];
bool v[1 + N_MAX][1 + M_MAX];
bool temp[1 + N_MAX][1 + M_MAX];

void roteste90()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            temp[j][n - i + 1] = v[i][j];
    swap(n, m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            v[i][j] = temp[i][j];
}

int main()
{
    cin >> n >> m >> ws;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin.get(c);
            v[i][j] = c - '0';
        }
        cin.get();
    }
    for(int k = 0; k < 4; k++)
    {
        for(int j = 1; j <= m; j++)
            h[j] = 0;
        for(int i = 1; i <= n; i++)
        {
            int vf = 0;
            sol[k][i] = sol[k][i - 1];
            for(int j = 1; j <= m + 1; j++)
            {
                if(v[i][j] == 0 && j <= m)
                    h[j]++;
                else
                    h[j] = 0;
                int s = 0;
                while(st[vf].first >= h[j] && vf > 0)
                {
                    s += st[vf].second;
                    sol[k][i] = max(sol[k][i], s * st[vf].first);
                    vf--;
                }
                st[++vf] = make_pair(h[j], s + 1);
            }
        }
        roteste90();
    }
    for(int i = 1; i < n; i++)
        amax = max(amax, sol[0][i] + sol[2][n - i]);
    for(int j = 1; j < m; j++)
        amax = max(amax, sol[1][j] + sol[3][m - j]);
    cout << amax;
    return 0;
}