Cod sursa(job #187669)

Utilizator DastasIonescu Vlad Dastas Data 5 mai 2008 00:27:52
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>

const int maxn = 201;
const int inf = - (1 << 30);

FILE *in = fopen("bmatrix.in","r"), *out = fopen("bmatrix.out","w");

int n, m;
int a[maxn][maxn];
int b[maxn][maxn];

void read()
{
    char buf[maxn + 1];

    fscanf(in, "%d %d", &n, &m);

    for ( int i = 1; i <= n; ++i )
    {
        fscanf(in, "%s", buf);

        for ( int j = 0; buf[j]; ++j )
            if ( buf[j] == '0' )
                a[i][j + 1] = 1;
            else
                a[i][j + 1] = - (1 << 20);
    }
}

inline int max(int x, int y)
{
    return x > y ? x : y;
}

int getmax(int startx, int starty, int endx, int endy)
{
    int maxsum = inf;

    for ( int i = starty; i <= endy; ++i )
        for ( int j = i; j <= endy; ++j )
        {
            int sum = inf;

            for ( int k = startx; k <= endx; ++k )
            {
                int t = b[k][j] - b[k][i-1];

                sum = max(sum+t, t);
                maxsum = max(maxsum, sum);
            }
        }

    return maxsum;
}

int main()
{
    read();

    int maxarea = -1;

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            b[i][j] = b[i][j-1] + a[i][j];

    for ( int i = 1; i < n; ++i )
    {
        int t1 = getmax(1, 1, i, m);
        int t2 = getmax(i+1, 1, n, m);

        maxarea = max(maxarea, t1 + t2);
    }

    for ( int i = 1; i < m; ++i )
    {
        int t1 = getmax(1, 1, n, i);
        int t2 = getmax(1, i+1, n, m);

        maxarea = max(maxarea, t1 + t2);
    }

    fprintf(out, "%d\n", maxarea);

    return 0;
}