Cod sursa(job #275767)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 10 martie 2009 17:33:12
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<algorithm>
#define DIM 301
using namespace std;
int n,m,x,a[DIM][DIM],sol[DIM][DIM];
void solve(){
	int i,j,s,st,dr,max;
	scanf("%d%d%d",&n,&m,&x);
	for(i=1; i<=n; ++i)
		for(j=1; j<=m; ++j){
			scanf("%d",&a[i][j]);
			a[i][j]+=a[i][j-1];}
	for(i=1; i<=m; sol[1][i]=a[1][i],++i);
	for(i=2; i<=n; ++i)
		for(j=1; j<=m; ++j)
			sol[i][j]=sol[i-1][j]+a[i][j];
	for(i=max=0; i<n; ++i)
		for(j=i+1; j<=n; ++j)
            for(st=dr=1,s=0; dr<=m; ++dr){
                s+=sol[j][dr]-(sol[j][dr-1]+sol[i][dr]-sol[i][dr-1]);
                for(; st<=dr&&s>x; s-=sol[j][st]-(sol[j][st-1]+sol[i][st]-sol[i][st-1]),++st);
				if(st<=dr&&(j-i)*(dr-st+1)>max)
					max=(j-i)*(dr-st+1);}
	printf("%d",max);}
int main(){
	freopen("teren.in","r",stdin);
	freopen("teren.out","w",stdout);
	solve();
	return 0;}