Cod sursa(job #1525870)

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

using namespace std;

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

const int NMAX = 300;

int N, M, K, Ans = 0, v[NMAX+2][NMAX+2], s[NMAX+2][NMAX+2];

int main() {
    in >> N >> M >> K;
    for( int i = 1;  i <= N;  ++i ) {
        for( int j = 1;  j <= M;  ++j ) {
            in >> v[i][j];
            s[i][j] = s[i-1][j] + v[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;
}