Cod sursa(job #276578)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 11 martie 2009 11:18:47
Problema Teren Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>

using namespace std;

ifstream fin ("teren.in");
ofstream fout ("teren.out");

char mat[303][303];
char M[303][303];
int n,m,A_max,NR;

void citire()
{
     int x;
     fin>>n>>m>>NR;
     for (int i=1;i<=n;i++)
          for (int j=1;j<=m;j++)
          {
               fin>>x;
               mat[i][j]=x;
               M[i][j]=M[i-1][j]+mat[i][j];
          }
}

inline int max(int a,int b)
{
     return a>b?a:b;
}

/*int main()
{
     int st,S,l1,l2,dr;
     citire();
     for (l1=1;l1<=n;l1++)
          for (l2=l1;l2<=n;l2++)
          {
               for (dr=1;dr<=m;dr++)
               {
                    st=dr;
                    S=0;
                    while (S<=NR && st<=m)
                    {
                         S+=M[l2][st]-M[l1-1][st];
                         if (S<=NR)
                              A_max=max(A_max,(st-dr+1)*(l2-l1+1));
                         st++;
                    }
                    if (S<=NR)
                         A_max=max(A_max,(st-dr+1)*(l2-l1+1));
               }
          }
     fout<<A_max;
     return 0;
}
*/


int main()
{
     int st,S,l1,l2,dr;
     citire();
     for (l1=1;l1<=n;l1++)
          for (l2=l1;l2<=n;l2++)
          {
               st=1;
               S=0;
               for (dr=1;dr<=m;dr++)
               {
                    S=M[l2][dr]-M[l1-1][dr];
                    while (st<=dr && S>NR)
                    {
                         S-=M[l2][st]-M[l1-1][st];
                         st++;
                    }
                         if (st<=dr)
                              A_max=max(A_max,(dr-st+1)*(l2-l1+1));
               }
          }
     fout<<A_max;
     return 0;
}