Cod sursa(job #221918)

Utilizator floringh06Florin Ghesu floringh06 Data 18 noiembrie 2008 20:14:06
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.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;
    }