Cod sursa(job #2734141)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 31 martie 2021 14:24:27
Problema Teren Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#include <ctype.h>// pentru isdigit() ca este mai rapid decat '0' <= ch && ch <= '9' deoarece foloseste un vector de frecventa

#define MAXN 300

int sum[1 + MAXN + 1][1 + MAXN + 1];// bordam matricea

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit(ch = fgetc(fin)) );
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n;
}

static inline int getPartialSum( int l1, int c1, int l2, int c2 ){
  return sum[l2][c2] - sum[l2][c1 - 1] - sum[l1 - 1][c2] + sum[l1 - 1][c1 - 1];
}

int main(){
  fin  = fopen("teren.in",  "r");
  fout = fopen("teren.out", "w");

  int n, m, l, c, maxarea, lmax, maxs, area;
  int l1, l2, c1, c2;

  n = fgetint();
  m = fgetint();
  maxs = fgetint();

  for( l = 1 ; l <= n ; l++ )// numerotam de la 1 ca matricea este bordata pentru sume partiale
    for( c = 1 ; c <= m ; c++ )
      sum[l][c] = fgetint();
  
  for( l = 0 ; l < n + 2 ; l++ )
    sum[l][m + 1] = 90001;

  // calculam sumele partiale
  for( l = 1 ; l <= n ; l++ )
    for( c = 1 ; c < m + 2 ; c++ )
      sum[l][c] += (sum[l - 1][c] + sum[l][c - 1] - sum[l - 1][c - 1]);

  maxarea = 0;
  for( l1 = 1 ; l1 <= n ; l1++ ){// fixam doua linii
    for( l2 = l1 ; l2 <= n ; l2++ ){
      c2 = 1;
      lmax = 0;
      for( c1 = 1 ; c1 <= m ; c1++ ){
        while( getPartialSum(l1, c1, l2, c2) <= maxs )
          c2++;
        lmax = (c2 - c1) > lmax ? (c2 - c1) : lmax;
      }
      
      area = lmax * (l2 - l1 + 1);// calculam aria maxima pe banda (l1, l2)
      maxarea = area > maxarea ? area : maxarea;
    }
  }

  fprintf(fout, "%d\n", maxarea);

  fclose(fin);
  fclose(fout);
  return 0;
}