Cod sursa(job #221918)
Utilizator | 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;
}