Cod sursa(job #1721535)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 25 iunie 2016 20:14:49
Problema BMatrix Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int mafia = 205;
int n,m,a[mafia][mafia],sol,b[mafia][mafia],s1[mafia][mafia];
int v[mafia],dp1[mafia],dp2[mafia],s2[mafia][mafia];
int stg[mafia],drp[mafia];
stack < pair < int, int > > st;
inline int Check()
{
    int i,j,sum = 0;
    while(!st.empty()) st.pop();
    stg[1] = 0;
    st.push(make_pair(v[1],1));
    for(i = 2; i <= m; i++)
    {
        while(!st.empty() && st.top().first >= v[i]) st.pop();
        if(v[i]==v[i-1]) stg[i] = stg[i-1]+1;
        else if(v[i] > v[i-1]) stg[i] = 0;
        else
        {
            if(st.empty()) stg[i] = i-1;
            else stg[i] = (i-st.top().second-1);
        }
        st.push(make_pair(v[i],i));
    }
    while(!st.empty()) st.pop();
    drp[m] = 0;
    st.push(make_pair(v[m],m));
    for(i = m-1; i > 0; i--)
    {
        while(!st.empty() && st.top().first >= v[i]) st.pop();
        if(v[i]==v[i+1]) drp[i] = drp[i+1]+1;
        else if(v[i] > v[i+1]) drp[i] = 0;
        else
        {
            if(st.empty()) drp[i] = (n-i);
            else drp[i] = (st.top().second - i - 1);
        }
        st.push(make_pair(v[i],i));
    }

    for(i = 1; i <= m; i++)
        sum = max(sum,(stg[i] + drp[i] + 1)*v[i]);
    return sum;
}

inline void Solve(int d[205][205])
{
    int i,j,x;
    for(i = 1; i <= n; i++) dp1[i] = dp2[i] = 0;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            s1[i][j] = (d[i][j] == 0? 1 + s1[i-1][j] : 0);
    for(i = n; i >= 1; i--)
        for(j = 1; j <= m; j++)
            s2[i][j] = (d[i][j] == 0? 1 + s2[i+1][j] : 0);

    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            v[j] = s1[i][j];
        x = Check();
        dp1[i] = max(dp1[i-1],x);
    }
    for(i = n; i >= 1; i--)
    {
        for(j = 1; j <= m; j++)
            v[j] = s2[i][j];
        x = Check();
        dp2[i] = max(dp2[i+1],x);
    }
    for(i = 1; i < n; i++)
        sol = max(sol,dp1[i] + dp2[i+1]);
}

int main()
{
    int i,j;
    char x;
    fin >> n >> m;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
    {
        fin >> x;
        a[i][j] = x - '0';
        b[j][i] = x - '0';
    }
    Solve(a);
    swap(n,m);
    Solve(b);
    fout << sol;
    fout.close();
    return 0;
}