Cod sursa(job #385461)

Utilizator laurpoppopescu laurentiu laurpop Data 22 ianuarie 2010 19:16:23
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>
FILE *fin, *fout;
int n,m,k,a[301][301],i,j,st,dr,s,max,x;

int main(){

	fin=fopen("teren.in","r");
	fout=fopen("teren.out","w");

	fscanf(fin,"%d %d %d",&n,&m,&k);

	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			fscanf(fin,"%d",&x);
			a[i][j]=a[i-1][j]+x;
		}
	}

	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			st=1;s=0;
			for(dr=1;dr<=m;dr++){
				s=s+a[j][dr]-a[i-1][dr];
				while(s>k && st<=dr){
					s=s-a[j][st]+a[i-1][st];
					st++;
				}
				if(st<=dr){
				    //	s+=a[j][dr]-a[i-1][dr];
					if( (j-i+1)*(dr-st+1)>max ){
						max=(j-i+1)*(dr-st+1);
					}
				}
			}
		}
	}

	fprintf(fout,"%d",max);


	fclose(fout);
	fclose(fin);

return 0;
}