Cod sursa(job #972043)

Utilizator poptibiPop Tiberiu poptibi Data 10 iulie 2013 21:05:17
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
//Imi fixez un colt si latura verticala
//Ma mut cu 2 pointeri cu ajutorul vectorului de sume partiale pe coloane etc

#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 i = 1; i <= N; ++ i)
        for(int k = i; k <= N; ++ k)
        {
            int Ptr = 1, S = 0;
            for(int j = 1; j <= M; ++ j)
            {
                while(Ptr <= M && S + Sum[k][Ptr] - Sum[i - 1][Ptr] <= X)
                {
                    S += Sum[k][Ptr] - Sum[i - 1][Ptr];
                    Ptr ++;
                }
                if(S <= X) Ans = max(Ans, (k - i + 1) * (Ptr - j));
                S -= Sum[k][j] - Sum[i - 1][j];
            }
        }

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