Cod sursa(job #498043)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 3 noiembrie 2010 21:47:53
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream.h>
#define NMAX 305

int i, n, m, x, j, amax, sum, st, dr, k;
short s[NMAX][NMAX], b[NMAX];

int main()
{
	ifstream f("teren.in");
	ofstream g("teren.out");
	
	f>>n>>m>>x;
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j) 
			{
				f>>s[i][j];
				s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			}
	amax=0;
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			for (k=1; k<=m; ++k)
				b[k]=s[j][k]-s[j][k-1]-s[i-1][k]+s[i-1][k-1];
			sum=0;st=1;
			for (dr=1; dr<=m; ++dr)
				if (sum+b[dr]<=x) sum+=b[dr];
					else break;
			--dr;
			if (dr*(j-i+1)>amax) amax=dr*(j-i+1);
			while (dr<=m && st<=dr)
			{
				sum-=b[st++];
				while (sum+b[dr+1]<=x && dr+1<=m) sum+=b[++dr];
				if ((dr-st+1)*(j-i+1)>amax) amax=(dr-st+1)*(j-i+1);
			}
		}
	g<<amax<<"\n";
	f.close();
	g.close();
	return 0;
}