Cod sursa(job #1525877)

Utilizator felixiPuscasu Felix felixi Data 15 noiembrie 2015 17:53:39
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in("teren.in");
ofstream out("teren.out");

const int NMAX = 300;

short int N, M, K,  s[NMAX+2][NMAX+2];

int Ans = 0;

int main() {
    in >> N >> M >> K;
    for( int i = 1;  i <= N;  ++i ) {
        for( int j = 1;  j <= M;  ++j ) {
            in >> s[i][j];
            s[i][j] = s[i-1][j] + s[i][j];
        }
    }
    for( int i = 1;  i <= N;  ++i ) {
        for( int j = i;  j <= N;  ++j ) {
            int ind = 1, sum = 0;

            for( int k = 1;  k <= M;  ++k ) {
                sum += ( s[j][k] - s[i-1][k] );

                while( sum > K ) {
                    sum -= ( s[j][ind] - s[i-1][ind] );
                    ++ind;
                }

                Ans = max( Ans, (j - i + 1) * (k - ind + 1) );
            }
        }
    }
    out << Ans << '\n';
    return 0;
}