Cod sursa(job #416748)

Utilizator bora_marianBora marian bora_marian Data 13 martie 2010 13:25:43
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
using namespace std;
int n,m,x;
int s[304][304],sol;
void solve();
int main()
{
	ifstream fin("teren.in");
	ofstream fout("teren.out");
	fin>>n>>m>>x;
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			fin>>s[i][j];
	for(i=1;i<=n;i++)
	   for(j=1;j<=m;j++)
		   s[i][j]=s[i-1][j]+s[i][j];
	
	solve();
    fout<<sol;
	return 0;
}

void solve ()
{
	int dq[303], st, dr, i, j, k, dqp[303];
	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);
			}
		}
}