Cod sursa(job #300388)

Utilizator lucaz0rLuca Liviu lucaz0r Data 7 aprilie 2009 13:33:39
Problema Teren Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <stdlib.h>
#define a(i,j) a[(i)*n+(j)]
#define b(i,j) b[(i)*n+(j)]
#define c(i,j) c[(i)*n+(j)]
int m, n;

void showmat(int *c) {
	int i, j;
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) printf ("%d ", c(i,j));
		printf ("\n"); }
	}

int main() {
	int  i, j, x,ok, count, max, cj, ci, li, lj, surf, s;
	int *a, *b;


	freopen ("teren.in", "r", stdin);
	freopen ("teren.out", "w", stdout);

	scanf ("%d %d %d", &m, &n, &x);

	a = malloc ((n+1) * (n+1) * sizeof(int));
	b = malloc ((n+1) * (n+1) * sizeof(int));

	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			scanf ("%d", &a(i,j));


	for (j = 0; j < n; j++)
		  { count = 0;
			for (i = 0; i < m; i++)
			{ if( a(i,j) == 1) count++;
			  b(i,j) = count; }
		  }
	max = 0;
	for (li = 0; li < m; li++)
		for (lj = li; lj < m; lj++)
		{
			cj = 0; s=0; ci = 0; ok=0;
			while(ci <= n)
				{
				 if (ci < n )
				 //showmat (b);
				 if (li>0)  s = s + b(lj,ci) - b(li-1,ci);
					else s = s + b(lj,ci);
				 if(s > x) { surf = (lj-li+1)*(ci-cj);
							ok = 1;
							  if(surf > max) max = surf;
							  for (j = cj; j < ci; j++)
								{ if (li>0) s = s - b(lj,j) + b(li-1,j);
									else s = s - b(lj,j);
								  if (s < x) { cj = j+1;
											   break; }}
							  if (s >= x) cj = ci;
						   }

				 if (ok == 0 && ci == n-1)
					   surf = (lj-li+1)*(ci-cj+1);
				 if (surf > max ) max = surf;
				 ci++;
				 }
		 }




	printf ("%d\n",max);


	free (a);
	free (b);





	/*showmat (a);
	printf ("\n");
	showmat (b);*/



	return 0;
 }