Cod sursa(job #275120)

Utilizator DraStiKDragos Oprica DraStiK Data 10 martie 2009 11:14:38
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>
#define DIM 305
int a[DIM][DIM],s[DIM][DIM];
int v[DIM];
int n,m,x,max;
void read ()
{
    int i,j;
    scanf ("%d%d%d",&n,&m,&x);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            scanf ("%d",&a[i][j]);
}
void proc ()
{
    int i,j;
    for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j)
			s[i][j]=s[i-1][j]+a[i][j];
}
void secv (int i,int j)
{
	int sum=0,st=1,dr;
	for (dr=1; dr<=m; ++dr)
	{
		sum+=v[dr];
		while (st<=dr && sum>x)
			sum-=v[st++];
		if (st<=dr && (j-i+1)*(dr-st+1)>max)
			max=(j-i+1)*(dr-st+1);
	}
}
void solve ()
{
	int i,j,k;
	for (i=1; i<=n; ++i)
		for (j=i; j<=n; ++j)
		{
			for (k=1; k<=m; ++k)
				v[k]=s[j][k]-s[i-1][k];
			secv (i,j);
		}
    printf ("%d",max);
}
int main ()
{
    freopen ("teren.in","r",stdin);
    freopen ("teren.out","w",stdout);    
    read ();
    proc ();
    solve ();
    return 0;
}