Cod sursa(job #221832)

Utilizator dgoldenAlex Popescu dgolden Data 18 noiembrie 2008 13:01:40
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "teren.in"
#define FOUT "teren.out"
#define MAX_N 305

int Map[MAX_N][MAX_N];

int D[MAX_N][MAX_N];
int A[MAX_N];

int BEST;
int N, M, X;

    inline int MAX (int a, int b)
    {
           if (a > b) return a; else return b;
    }

    void preproc ()
    {
         int i, j;
         for (j = 1; j <= M; ++j)
             for (i = 1; i <= N; ++i)
                 D[i][j] = D[i - 1][j] + Map[i][j];
    }

    int main ()
    {
        int i, j, l1, l2, k, li, lf, sum;
        
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d %d", &N, &M, &X);
        for (i = 1; i <= N; ++i)
            for (j = 1; j <= M; ++j)
                scanf ("%d", Map[i] + j);
                
        preproc ();
        for (l1 = 1; l1 <= N; ++l1)
            for (l2 = l1; l2 <= N; ++l2)
            {
                for (k = 1; k <= M; ++k) A[k] = D[l2][k] - D[l1 - 1][k];
                
                li = 1, sum = 0;
                for (lf = 1; lf <= M; ++lf)
                {
                    sum += A[lf];
                    while (li <= lf && sum > X) sum -= A[li++];
                    if (li <= lf)
                         BEST = MAX (BEST, (l2 - l1 + 1) * (lf - li + 1));
                }                
            }
        printf ("%d\n", BEST);

        return 0;
    }