Cod sursa(job #461268)

Utilizator SpiderManSimoiu Robert SpiderMan Data 6 iunie 2010 09:58:48
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>

const char FIN[] = "teren.in", FOU[] = "teren.out";
const int MAX_N = 305;

int V[MAX_N][MAX_N], sum[MAX_N][MAX_N];
int A[MAX_N];
int N, M, K;

int main()
{
    freopen(FIN , "r" , stdin);
    freopen(FOU , "w" , stdout);

    scanf("%d %d %d", &N, &M, &K);

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            scanf("%d", &V[i][j]), sum[i][j] = sum[i - 1][j] + V[i][j];

    int sol = 0;

    for (int i = 1; i < N; ++i)
        for (int j = i + 1; j <= N; ++j)
        {
            for (int k = 1; k <= M; ++k)
                A[k] = sum[j][k] - sum[i - 1][k];

            for (int dr = 1, st = 1, suma = 0; dr <= M; ++dr)
            {

                for ( suma += A[dr]; st <= dr && suma > K; ++st)
                    suma -= A[st];

                if ( st <= dr && sol < ( j - i + 1 ) * ( dr - st + 1 ) )
                    sol = ( j - i + 1 ) * ( dr - st + 1 );
            }
        }

    printf("%d", sol);

    return 0;
}