Cod sursa(job #971923)

Utilizator poptibiPop Tiberiu poptibi Data 10 iulie 2013 15:36:23
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define Nmax 310

int N, M, X, Mat[Nmax][Nmax], Sum[Nmax][Nmax], Ans;

int main()
{
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);

    scanf("%i %i %i", &N, &M, &X);
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
        {
            scanf("%i", &Mat[i][j]);
            Sum[i][j] = Sum[i - 1][j] + Mat[i][j];
        }

    for(int Up = 1; Up <= N; ++ Up)
        for(int i = 1; i + Up - 1 <= N; ++ i)
        {
            int Ptr = 1, S = 0;
            for(int j = 1; j <= M; ++ j)
            {
                while(Ptr <= M && S + Sum[i + Up - 1][Ptr] - Sum[i - 1][Ptr] <= X)
                {
                    S += Sum[i + Up - 1][Ptr] - Sum[i - 1][Ptr];
                    Ptr ++;
                }
                if(S <= X) Ans = max(Ans, Up * (Ptr - j));
                S -= Sum[i + Up - 1][j] - Sum[i - 1][j];
            }
        }

    printf("%i\n", Ans);
    return 0;
}