Cod sursa(job #2637006)

Utilizator euyoTukanul euyo Data 20 iulie 2020 21:37:09
Problema Teren Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>

using namespace std;

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

const int Lim = 302;

int M[Lim][Lim], S[Lim][Lim];

static inline int sum( int l1, int l2, int c ) {
  return S[l2][c] - S[l2][c - 1] - S[l1 - 1][c] + S[l1 - 1][c - 1];
}

int main() {
  int n, m, k, i, j, l1, l2, maxa, a, c1, c2, n1;
  
  fin >> n >> m >> k;
  for ( i = 1; i <= n; ++i ) {
	for ( j = 1; j <= m; ++j ) {
	  fin >> M[i][j];
	  S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + M[i][j];
	}
  }
  maxa = 0;
  for ( l1 = 1; l1 <= n; ++l1 ) {
	for ( l2 = l1; l2 <= n; ++l2 ) {
	  a = n1 = 0;
	  c1 = c2 = 1;
	  while ( c2 <= n ) {
		n1 += sum( l1, l2, c2 );
		a += l2 - l1 + 1;
		++c2;
		if ( n1 <= k ) {
		  if ( maxa < a ) {
			maxa = a;
		  }
		} else {
		  while ( n1 > k ) {
			n1 -= sum( l1, l2, c1 );
			a -= (l2 - l1 + 1);
		    ++c1;
		  }
		  if ( a > maxa ) {
            maxa = a;
		  }
		}
	  }
	}
  }
  fout << maxa; 
  fin.close();
  fout.close();
  return 0;
}