Cod sursa(job #2552654)

Utilizator Florinos123Gaina Florin Florinos123 Data 21 februarie 2020 08:26:49
Problema Teren Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>

using namespace std;

ifstream f ("teren.in");
ofstream g ("teren.out");

int a[305][305], suma[305][305], x, n, m;

void read ()
{
 int i, j;
  f >> n >> m >> x;
   for (i=1; i<=n; i++)
   {
       for (j=1; j<=m; j++)
       {
           f >> a[i][j];
       }
   }
}

void precalc ()
{
 int i, j;
  for (i=1; i<=n; i++)
  {
      for (j=1; j<=m; j++)
      {
          suma[i][j] = a[i][j] + suma[i-1][j] + suma[i][j-1] - suma[i-1][j-1];
      }
  }
}

int getsuma (int i, int j, int ii, int jj)
{
    return suma[ii][jj] - suma[ii][j-1] - suma[i-1][jj] + suma[i-1][j-1];
}

void solve ()
{
 int i, j, ii, jj, aria, aux, maxim = 0;
  for (i=1; i<=n; i++)
  {
      for (j=1; j<=m; j++)
      {
          for (ii=i; ii<=n; ii++)
          {
              for (jj=j; jj<=m; jj++)
              {
                  aux = getsuma(i, j, ii, jj);
                   if (aux <= x)
                   {
                       aria = (ii - i + 1) * (jj - j + 1);
                       maxim = max(maxim, aria);
                   }
              }
          }
      }
  }
 g << maxim;
}

int main()
{
read();
precalc();
solve();
  return 0;
}