Cod sursa(job #1042031)

Utilizator mvcl3Marian Iacob mvcl3 Data 26 noiembrie 2013 15:01:44
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

#define in "teren.in"
#define out "teren.out"
#define Max_Size 309

std :: ifstream f(in);
std :: ofstream g(out);

short N, M;
int X, Sol;

short A[Max_Size][Max_Size];
int S[Max_Size][Max_Size];

inline void Read_Data()
{
    f >> N >> M >> X;

    for(short i = 1; i <= N; ++i)
        for(short j = 1; j <= M; ++j)
            f >> A[i][j];
}

inline void Count()
{
    for(short i = 1; i <= N; ++i)
        for(short j = 1; j <= M; ++j)

            S[i][j] = A[i][j] + S[i - 1][j];
}

inline void Solve()
{
    for(int i = 1; i <= N; ++i)
        for(int k = i; k <= N; ++k)
        {
            int begin = 1, Sum = 0;

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

                while(Sum > X)
                {
                    Sum -= S[k][begin] - S[i - 1][begin];
                    ++begin;
                }

                Sol = std :: max( Sol, (j - begin + 1) * (k - i + 1) );
            }
        }
}

int main()
{
    Read_Data();
    Count();
    Solve();

    g << Sol << '\n';

    g.close();
    return 0;
}