Cod sursa(job #733527)

Utilizator danalex97Dan H Alexandru danalex97 Data 12 aprilie 2012 13:12:24
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <cstring>
using namespace std;

#define MAX_N 305
#define FIN "teren.in"
#define FOUT "teren.out"
#define max(a, b) ( ( a>b ) ? a : b )
#define min(a, b) ( ( a<b ) ? a : b )

int N, M, X, A[MAX_N][MAX_N], S[MAX_N], Res;

int main(void)
{
    int i, j, k, p, sum;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d %d %d", &N, &M, &X);
    for (i = 0; i < N; ++i)
        for (j = 0; j < M; ++j)
            scanf("%d", A[i]+j);

    for (i = 0; i < N; ++i)
    {
        memset(S, 0, sizeof(S));
        for (j = i; j < N; ++j)
            for (p = sum = k = 0; k < M; ++k)
            {
                S[k] += A[j][k] , sum += S[k];
                
				for (; p <= k && sum > X; ++p) sum -= S[p];
                
				if (p > k) continue;
                Res = max(Res, (j-i+1)*(k-p+1)); 
            }
    }

    printf("%d\n", Res);
}