Cod sursa(job #1909516)

Utilizator robx12lnLinca Robert robx12ln Data 7 martie 2017 12:57:50
Problema Teren Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<cstdio>
#include<algorithm>
using namespace std;
FILE * fin = fopen("teren.in","r");
FILE * fout = fopen("teren.out","w");
char a[305][305];
int D[305][305], n, m, aria, x, sol, st, sum;
int main(){
    fscanf( fin, "%d%d%d", &n, &m, &x );
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            fscanf( fin, "%s", &a[i][j] );
        }
    }
    //D[i][j] = cati de unu sunt pe colona j pana la linia i inclusiv
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            D[i][j] = D[i - 1][j] + (a[i][j] - '0');
        }
    }
    for( int i1 = 1; i1 <= n; i1++ ){
        for( int i2 = i1; i2 <= n; i2++ ){
            st = 1;
            sum = D[i2][1] - D[i1 - 1][1];
            aria = (i2 - i1 + 1);
            for( int j = 2; j <= m; j++ ){
                if( sum + D[i2][j] - D[i1 - 1][j] <= x ){
                    sum += D[i2][j] - D[i1 - 1][j];
                    aria = (i2 - i1 + 1) * (j - st + 1);
                }else{
                    while( sum + D[i2][j] - D[i1 - 1][j] > x && st < j ){
                        sum -= ( D[i2][st] - D[i1 - 1][st] );
                        st++;
                    }
                    sum += D[i2][j] - D[i1 - 1][j];
                    aria = (i2 - i1 + 1) * (j - st + 1);
                }
                sol = max( sol, aria );
            }
            sol = max( sol, aria );
        }
    }
    fprintf( fout, "%d\n", sol );
    return 0;
}