Cod sursa(job #1995730)

Utilizator vladm98Munteanu Vlad vladm98 Data 28 iunie 2017 23:52:07
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;
int v[205];
int a[203][203];
int rotit[203][203];
int dp[4][203];
stack <int> sol;
int functie (int n)
{
    int maxim = 0;
    sol.push(0);
    for (int i = 1; i<=n+1; ++i)
    {
        while (v[sol.top()]>v[i])
        {
            int x = sol.top();
            sol.pop();
            maxim = max(maxim, v[x]*(i-sol.top()-1));
        }
        sol.push(i);
    }
    return maxim;
}
void roteste (int n, int m)
{
    for (int i = 0; i<=200; ++i)
        for (int j = 0; j<=200; ++j)
            rotit[i][j] = 0;
    for (int j = 1; j<=n; ++j)
        for (int i = 1; i<=m; ++i)
            rotit[i][j] = a[j][m-i+1];
    for (int i = 0; i<=200; ++i)
        for (int j = 0; j<=200; ++j)
            a[i][j] = 0;
    for (int i = 1; i<=m; ++i)
        for (int j = 1; j<=n; ++j)
            a[i][j] = rotit[i][j];
}
int main()
{
    ifstream fin ("bmatrix.in");
    ofstream fout ("bmatrix.out");
    int n, m;
    fin >> n >> m;
    fin.get();
    for (int i = 1; i<=n; ++i)
    {
        for (int j = 1; j<=m; ++j)
        {
            char c;
            c = fin.get();
            a[i][j] = (int)(c-'0')^1;
        }
        fin.get();
    }
    int x = n, y = m;
    for (int d = 0; d<4; ++d)
    {
        for (int i = 1; i<=y; ++i)
            v[i] = 0;
        for (int i = 1; i<=x; ++i)
        {
            for (int j = 1; j<=y; ++j)
            {
                if (a[i][j])
                    ++v[j];
                else v[j] = 0;
            }
            dp[d][i] = max (dp[d][i-1], functie(y));
        }
        roteste(x, y);
        swap(x, y);
    }
    int raspuns = 0;
    for (int i = 0; i<=n; ++i)
        raspuns = max(raspuns, dp[0][i]+dp[2][n-i]);
    for (int i = 0; i<=m; ++i)
        raspuns = max (raspuns, dp[1][i]+dp[3][m-i]);
    fout << raspuns;
    return 0;
}