Cod sursa(job #276167)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 10 martie 2009 22:03:38
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>

int s[301][301];
int n,m,x,am,a[3001];

void citire()
{
  scanf("%d %d %d",&n,&m,&x);
  int x;
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
     {scanf("%d",&x);
      s[i][j]=x+s[i-1][j];
      }
}

int max(int a,int b)
{
 if(a>b) return a;
 else return b;
}

void vad(int i,int j)
{
  int st=1,sum=0;
  for(int dr=1;dr<=m;dr++)
  {sum+=a[dr];
   while(st<=dr&&sum>x)
   {
    sum-=a[st];
    st++;
    }

    if(st<=dr)
     am=max(am,(j-i+1)*(dr-st+1));
   }

}

void solve()
{
  for(int i=1;i<=n;i++)
   for(int j=i;j<=n;j++)
     {
      for(int k=1;k<=m;k++)
	a[k]=s[j][k]-s[i-1][k];
      vad(i,j);
     }

  printf("%d",am);
}


int main()
{
  freopen("teren.in","r",stdin);
  freopen("teren.out","w",stdout);
  citire();
  solve();
  return 0;
}