Cod sursa(job #110636)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 noiembrie 2007 09:25:11
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
int x[302][302], s[302][302], a[302], n, m, k;

void citire()
{
   freopen("teren.in","r",stdin);
   freopen("teren.out","w",stdout);
   int i, j;
   scanf("%d%d%d", &n, &m, &k);
   for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
      {
	 scanf("%d",&x[i][j]);
	 s[i][j] = s[i - 1][j] + x[i][j];
      }
}

int main()
{
  citire();
  int i, j, l, st, dr, suma, max = 0;
  for (i = 1; i < n; i++)
    for (j = i + 1; j <= n; j++)
    {
      for (l = 1; l <= m; l++)
	a[l] = s[j][l] - s[i - 1][l];
      st = 1;
      suma = 0;
      for (dr = 1; dr <= m; dr++)
      {
	suma += a[dr];
	while (st <= dr && suma > k)
	{
	   suma -=a[st];
	   st++;
	}
	if (st <= dr && max < (j - i + 1)* (dr - st + 1))
	  max = (j - i + 1)*(dr - st + 1);
      }
    }
  printf("%d\n",max);
  return 0;
}