Cod sursa(job #1752440)

Utilizator silkMarin Dragos silk Data 3 septembrie 2016 22:21:14
Problema Teren Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#define NMax 300

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,ii,ans,temp;

    scanf("%d %d %d\n",&N,&M,&X);
    for(i = 1; i <= N; ++i)
    {
        fgets( s, 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)
        {
            ii = jj = 1; temp = 0;
            while( temp <= X && jj <= M ) { temp += sum[jj][j] - sum[jj][i-1]; ++jj; }
            if( (j-i+1)*(jj-ii-1) > ans ) ans = (j-i+1)*(jj-ii-1);

            while( jj < M )
            {
                while( temp > X )
                {
                    temp -= sum[ii][j] - sum[ii][i-1];
                    ++ii;
                }

                while( temp <= X && jj <= M)
                {
                    temp += sum[jj][j] - sum[jj][i-1];
                    ++jj;
                }

                if( (j-i+1)*(jj-ii-1) > ans ) ans = (j-i+1)*(jj-ii-1);
            }
        }


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



return 0;
}