Cod sursa(job #120273)

Utilizator hadesgamesTache Alexandru hadesgames Data 4 ianuarie 2008 19:12:04
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
int a[301][301],b[301][301];
int main()
{
	FILE *in,*out;
	int n,m,x,max,i,j,k,p,t;
	in=fopen("teren.in","r");
	out=fopen("teren.out","w");
	fscanf(in,"%d%d%d",&n,&m,&x);
	for (i=0;i<=n;i++)
		a[i][0]=0;
	for (j=0;j<=m;j++)
		a[0][j]=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			fscanf(in,"%d",&a[i][j]);
	max=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
			if (a[i][j])
				b[i][j]++;
			if (b[i][j]<=x&&i*j>max)
				max=i*j;
		}
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			t=0;
			p=1;
			for (k=1;k<=m;k++)
			{
				t+=b[j][k]-b[i-1][k]-b[j][k-1]+b[i-1][k-1];
				while (t>x&&p<=k)
				{
					t-=b[j][p]-b[i-1][p]-b[j][p-1]+b[i-1][p-1];
					p++;
				}
				if (t<=x&&(j-i+1)*(k-p+1)>max)
					max=(j-i+1)*(k-p+1);
			}
				
		}			
	fprintf(out,"%d\n",max);
	fclose(in);
	fclose(out);
	return 0;
}