Cod sursa(job #199346)

Utilizator zbarniZajzon Barna zbarni Data 17 iulie 2008 23:47:36
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream.h>
#define g 310
short a[g],s[g][g],t[g][g];

int main()
 {
  ifstream be ("teren.in");
  int n,m,i,j,x;
  be>>n>>m>>x;
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
    be>>t[i][j];
  be.close();
  ofstream ki ("teren.out");

  long mxt=0,sum,r,dr,st;
  for (i=1;i<n;i++)
    {
     for (r=1;r<=m;r++)
       s[i][r]=t[i][r];
     for (j=i+1;j<=n;j++)
      {
       for (r=1;r<=m;r++)
	{
	 s[j][r]=s[j-1][r]+t[j][r];
	}
       st=1; sum=0;
       for (dr=1;dr<=m;dr++)
	{
	 sum+=s[j][dr];
	 while (st<=dr && sum>x)
	   {
	    sum-=s[j][st];
	    st++;
	   }
	 if (st<dr && mxt<(j-i+1)*(dr-st+1))
	   mxt=(j-i+1)*(dr-st+1);
	}
      }
    }
  ki<<mxt<<"\n";
  ki.close();
  return 0;
 }