Cod sursa(job #1752446)

Utilizator silkMarin Dragos silk Data 3 septembrie 2016 22:56:49
Problema Ordine Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#define NMax 301

int sum[NMax+1][NMax+1];
char a[NMax+1][NMax+1];
char s[2*NMax+1];

int main(){
    freopen("teren.in","r",stdin);
    freopen("teren.out","w",stdout);

    int N,M,X,i,j,jj,k,p,ans,temp,ok;

    scanf("%d %d %d\n",&N,&M,&X);
    for(i = 1; i <= N; ++i)
    {
        fgets( s, 2*NMax-1, stdin );
        for(jj = 0, j = 1; j <= M; ++j, jj+=2) a[i][j] = s[jj] - '0';
    }

    for(i = 1; i <= N; ++i)
        for(j = 1; j <= M; ++j)
        sum[j][i] = sum[j][i-1] + (a[i][j]==1);

    for(ans = 0, i = 1; i <= N; ++i)
        for(j = i; j <= N; ++j)
        {
            temp = 0;
            for(p = k = 1; k <= M; ++k)
            {
                temp += sum[k][j] - sum[k][i-1];
                while( temp > X && p <= k )
                {
                    temp -= sum[p][j] - sum[p][i-1];
                    ++p;
                }
                if( (j-i+1)*(k-p+1) > ans ) ans = (j-i+1)*(k-p+1);
            }
        }


    printf("%d\n",ans);



return 0;
}