Cod sursa(job #155894)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 12 martie 2008 11:17:02
Problema Teren Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
# include <stdio.h>

const long int MAXN=300;

long int colup[MAXN+2][MAXN+2],coldown[MAXN+2][MAXN+2],total,a[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;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
	{
	fscanf(f,"%ld",&a[i][j]);
	col[j]+=a[i][j];
	}
fcloseall();
}

void init()
{
long int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
	colup[i][j]=colup[i-1][j]+a[i][j];
for (i=n;i>=1;i--)
for (j=1;j<=m;j++)
	coldown[i][j]=coldown[i+1][j]+a[i][j];
}

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+2;i2<=n+1;i2++)
	{
	for (j=1;j<=m;j++) colloc[j]=col[j]-colup[i1][j]-coldown[i2][j];
	solloc=get_maxwide();
	if (solloc*(i2-i1-1)>sol) sol=solloc*(i2-i1-1);
	}
}

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

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