Pagini recente » Cod sursa (job #2500677) | Cod sursa (job #2167802) | Cod sursa (job #2595491) | Cod sursa (job #1113958) | Cod sursa (job #2734141)
#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;
}