Cod sursa(job #1646963)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 10 martie 2016 18:24:06
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<iostream>
#include<fstream>
#include<vector>

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

int N, M, X, Lmax, lmax;
int a[303][303], v[303];

int main ()
{
  fin >> N >> M >> X;
  int i, j, x, L1, L2, s;

  for (i=1; i<=N; i++)
  {
    for (j=1; j<=M; j++)
     {
        fin >> x;  /// x poate fi 1 sau 0
        a[i][j] = a[i-1][j] + x;
     }
  }     /// sume partiale pe coloane

  /// fixam 2 linii L1 si L2

  Lmax = -2;

  for (L1=1; L1<N; L1++)
  {
    for (L2=L1+1; L2<=N; L2++)
    {
      /// v[i] numarul de 1 aflate pe coloana j
      /// intre liniile L1 si L2
      for (j=1; j<=M; j++)
      {
         v[j] = a[L2][j] - a[L1-1][j];

         /// cautam in vectorul v o secventa de lung maxima
         /// cu suma <= X
      }

      i = 1;
      s = 0;
      lmax = -1;

      for(j=1; j<=M; j++)
      {
         s += v[j];
         while (s > X) { s -= v[i]; i++;}
         lmax = max(lmax, j - i + 1);
      }
         lmax = lmax * (L2-L1+1);
         Lmax = max(Lmax, lmax);
    }
  }

  fout << Lmax << "\n";
  fin.close();
  fout.close();
  return 0;
}