Cod sursa(job #155927)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 12 martie 2008 11:33:19
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
# include <stdio.h>

const long int MAXN=300;

int colup[MAXN+2][MAXN+2],col[MAXN+2],colloc[MAXN+2];
long int sol=0,m,n,x;

void citire()
{
FILE *f=fopen("teren.in","r");
fscanf(f,"%ld%ld%ld",&n,&m,&x);
long int i,j,aa;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
	{
	fscanf(f,"%ld",&aa);
	col[j]+=aa;
	colup[i][j]=colup[i-1][j]+aa;
	}
fcloseall();
}

long int get_maxwide()
{
long int li=1,lf=0,inb=0,mw=0;
while (lf<m)
	{
	lf++;
	inb+=colloc[lf];
	while (li<=lf&&inb>x) inb-=colloc[li],li++;
	if (li<=lf&&lf-li+1>=mw) mw=lf-li+1;
	}
return mw;
}

void calculeaza()
{
long int solloc,i1,i2,j;
for (i1=0;i1<=n-1;i1++)
for (i2=i1+1;i2<=n;i2++)
	{
	for (j=1;j<=m;j++) colloc[j]=colup[i2][j]-colup[i1][j];
	solloc=get_maxwide();
	if (solloc*(i2-i1)>sol) sol=solloc*(i2-i1);
	}
}

void scrie()
{
FILE *g=fopen("teren.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

int main()
{
citire();
calculeaza();
scrie();
return 0;
}