Cod sursa(job #787377)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 13 septembrie 2012 11:40:57
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
#include<cmath>
using namespace std;
int n,m,X,sol;
int nrC[310][310],v[310];
//nrC[i][j]=numarul de 1 de pe coloana j pe portiunea dintre liniile 1 si i

int main()
{
	int i,j,k,nr,val,st,dr;
	ifstream fin("teren.in");
	fin>>n>>m>>X;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			fin>>val;
			nrC[i][j]=nrC[i-1][j]+val;
		}
	}
	fin.close();
	
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=1;k<=m;k++)
				v[k]=nrC[j][k]-nrC[i-1][k];
			st=1;
			dr=0;
			nr=0;
			while(dr<m)
			{
				dr++;
				nr+=v[dr];
				if(nr<=X)
					sol=max(sol,(dr-st+1)*(j-i+1));
				else
				{
					while(nr>X)
					{
						nr-=v[st];
						st++;
					}
				}
			}
		}
	}
	
	ofstream fout("teren.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}