Cod sursa(job #414305)

Utilizator loginLogin Iustin Anca login Data 9 martie 2010 22:06:15
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
# include <fstream>
using namespace std;
int n, m, x, t[303][303], s[303][303], sol;

void read ()
{
	ifstream fin ("teren.in");
	fin>>n>>m>>x;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			fin>>t[i][j];
			s[i][j]=s[i-1][j]+t[i][j];
		}
}

void solve ()
{
	int dq[400], st, dr, i, j, k, scur, dqp[400];
	for (i=0;i<n;i++)
		for (j=1;j<=n;j++)
		{
			st=dr=1;
			dq[st]=0;
			dqp[st]=0;
			for (k=1;k<=m;k++)
			{
				dq[++dr]=dq[dr-1]+s[j][k]-s[i][k];
				dqp[dr]=k;
				while (dq[dr]-dq[st]>x && st<dr)++st;
				if ((k-dqp[st])*(j-i)>sol)
					sol=(k-dqp[st])*(j-i);
			}
		}
}			

int main ()
{
	read ();
	solve ();
	ofstream fout ("teren.out");
	fout<<sol;
	return 0;
}