Cod sursa(job #1995518)

Utilizator LucaSeriSeritan Luca LucaSeri Data 28 iunie 2017 12:14:27
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <fstream>
#include <stack>

using namespace std;
int dp[202][202];

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



int arielin(int lin, int m, int n){
        stack<int> h;
        h.push(0);
        int ds[202][202];
        int maxup = -1;
        for(int i = 1; i <= lin; i++)
        {
            for(int j = 1; j <= n+1; j++)
            {
                while(dp[i][j] < dp[i][h.top()])
                {
                    int val = dp[i][h.top()];
                    h.pop();
                    int arie = val*(j-h.top()-1);
                    if(arie > maxup) maxup = arie;
                }
                h.push(j);
            }
        }

        int maxdown = -1;
        while(h.size()) h.pop();
        h.push(0);
        for(int i = lin+1; i <= m; i++){
            for(int j = 1; j <= n+1; j++){
                if(dp[i][j] > i-lin) ds[i][j] = dp[i][j] - dp[lin][j];
                else ds[i][j] = dp[i][j];
            }
        }
        for(int i = lin+1; i <= m; i++)
        {
            for(int j = 1; j <= n+1; j++)
            {
                while(ds[i][j] < ds[i][h.top()])
                {
                    int val = ds[i][h.top()];
                    h.pop();
                    int arie = val*(j-h.top()-1);
                    if(arie > maxdown) maxdown = arie;
                }
                h.push(j);
            }
        }

    return maxup + maxdown;
}

int ariecol(int col, int m, int n)
{
        stack<int> h;
        int maxleft = -1;
        h.push(0);
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= col; j++)
            {
                while(dp[i][j] < dp[i][h.top()])
                {
                    int val = dp[i][h.top()];
                    h.pop();
                    int arie = val*(j-h.top()-1);
                    if(arie > maxleft) maxleft = arie;
                }
                h.push(j);
            }
            while(h.size() > 1)
            {
            int val = dp[i][h.top()];
            h.pop();
            int arie = val*(col - h.top());
            if(arie > maxleft) maxleft = arie;
            }
        }



        int maxright = -1;
        h.push(0);
        for(int i = 1; i <= m; i++)
        {
            for(int j = col + 1; j <= n+1; j++)
            {
                while(dp[i][j] < dp[i][h.top()])
                {
                    int val = dp[i][h.top()];
                    h.pop();
                    int arie = val*(j-h.top()-1);
                    if(arie > maxright) maxright = arie;
                }
                h.push(j);
            }
        }

    return maxleft + maxright;
}
int main()
{
    int m, n;
    f >> m >> n;
    char nr;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f >> nr;
            if(nr - '0' == 1) dp[i][j] = 0;
            else dp[i][j] = dp[i-1][j] + 1;
        }
    }
    int best = -1;
    for(int i = 1; i < m; i++){
        best = max(best, arielin(i, m, n));
    }

    for(int j = 1; j < n; j++){
        best = max(best, ariecol(j, m, n));
    }
    g << best;
    return 0;
}