Cod sursa(job #1512391)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 27 octombrie 2015 23:41:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <cstdio>
#include <algorithm>
#include <stack>

#define NMAX 225

using namespace std;
int n, m, ans, dp[4][NMAX], prec[NMAX], prec1[NMAX], prec2[NMAX];
char mat[NMAX][NMAX];

void solve1(const int &f)
{
    stack <int> stiva;
    for(int i = 1; i<= m; ++i) prec[i] = 0;
    for(int i = 1; i<= n; ++i)
    {
        for(int j = 1; j<= m; ++j)
        {
            if(mat[i][j] == '1') prec[j] = i;
        }
        while(!stiva.empty()) stiva.pop();
        for(int j = 1; j<= m; ++j)
        {
            while(!stiva.empty() && prec[stiva.top()] <= prec[j]) stiva.pop();
            prec1[j] = ((stiva.empty())?0:stiva.top());
            stiva.push(j);
        }
        while(!stiva.empty()) stiva.pop();
        for(int j = m; j; --j)
        {
            while(!stiva.empty() && prec[stiva.top()] <= prec[j]) stiva.pop();
            prec2[j] = ((stiva.empty()) ? m+1:stiva.top());
            stiva.push(j);
        }
        dp[f][i] = dp[f][i-1];
        for(int j = 1; j<= m; ++j)
            dp[f][i] = max(dp[f][i], (i - prec[j]) * (prec2[j] - prec1[j] - 1));
    }
}
void solve2(const int &f)
{
    stack <int> stiva;
    for(int i = 1; i<= n; ++i) prec[i] = 0;
    for(int j = 1; j<= m; ++j)
    {
        for(int i = 1; i <= n; ++i)
        {
            if(mat[i][j] == '1') prec[i] = j;
        }
        while(!stiva.empty()) stiva.pop();
        for(int i = 1; i<= n; ++i)
        {
            while(!stiva.empty() && prec[stiva.top()] <= prec[i]) stiva.pop();
            prec1[i] = ((stiva.empty()) ? 0 : stiva.top());
            stiva.push(i);
        }
        while(!stiva.empty()) stiva.pop();
        for(int i = n; i; --i)
        {
            while(!stiva.empty() && prec[stiva.top()] <= prec[i]) stiva.pop();
            prec2[i] = ((stiva.empty()) ? n + 1:stiva.top());
            stiva.push(i);
        }
        dp[f][j] = dp[f][j-1];
        for(int i = 1; i<= n; ++i)
            dp[f][j] = max(dp[f][j], (j - prec[i]) * (prec2[i] - prec1[i] - 1));
    }
}
void apel()
{
    solve1(0);
    for(int i = 1; i<= n/2; ++i) swap(mat[i], mat[n-i+1]);
    solve1(1);
    for(int i = 1; i<= n/2; ++i) swap(mat[i], mat[n-i+1]);
    solve2(2);
    for(int i = 1; i<= n; ++i)
        for(int j = 1; j<= m/2; ++j) swap(mat[i][j], mat[i][m-j+1]);
    solve2(3);
}
void reconstituire()
{
    for(int i = 1; i< n; ++i)
    {
        ans = max(ans, dp[0][i] + dp[1][n-i]);
        //printf("%d\n", dp[0][i] + dp[1][n-i]);
    }
    //printf("check\n");
    for(int i = 1; i< m; ++i)
    {
        ans = max(ans, dp[2][i] + dp[3][m-i]);
        //printf("%d\n", dp[2][i] + dp[3][m-i]);
    }
}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; ++i) scanf("%s", mat[i]+1);
   // for(int i = 1; i<= n; ++i)
   //     for(int j = 1; j<= m; ++j)
   //         mat[i][j] -= '0';
    apel();
    reconstituire();
    printf("%d\n", ans);
    return 0;
}