Cod sursa(job #153380)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 10 martie 2008 15:00:26
Problema Teren Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <fstream.h>

long a[310][310];
long n,m,nr;
long maxim;

void citire()
{
  freopen ("teren.in","r",stdin);
  scanf ("%ld%ld%ld",&n,&m,&nr);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
       scanf ("%ld",&a[i][j]);
  fclose (stdin);
}

void numarare()
{
   for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
	  a[i][j]+=a[i][j-1];
}

void afisare()
{
   for (int c1=1;c1<=m;c1++)
      for (int c2=c1;c2<=m;c2++)
      for (int l1=1;l1<=n;l1++)
      {
	 long poz=l1,S=0;
	 for (int linie=l1;linie<=n;linie++)
	 {
	    S+=a[linie][c2]-a[linie][c1-1];
	    if (S>nr)
	    {
	       S=0;
	       poz=linie+1;
	    }
	     else
	       if  ((linie-poz+1)*(c2-c1+1)>maxim)
		  maxim=(linie-poz+1)*(c2-c1+1);
	 }
      }
   freopen ("teren.out","w",stdout);
   printf ("%ld \n",maxim);
   fclose(stdout);
}

int main ()
{
   memset(a,0,sizeof(a));
   citire();
   numarare();
   afisare();
   return 0;
}