Cod sursa(job #1721498)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 25 iunie 2016 19:32:37
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 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 st[mafia],dr[mafia];

inline int Check()
{
    int i,j,sum = 0;
    st[1] = 0;
    for(i = 2; i <= m; i++)
    {
        if(v[i] > v[i-1]) st[i] = 0;
        else st[i] = st[i-1] + 1;
    }
    dr[m] = 0;
    for(i = m-1; i >= 1; i--)
    {
        if(v[i] > v[i+1]) dr[i] = 0;
        else dr[i] = dr[i+1]+1;
    }
    for(i = 1; i <= m; i++)
        sum = max(sum,(st[i] + dr[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;
}