Cod sursa(job #2958860)

Utilizator gripzStroescu Matei Alexandru gripz Data 28 decembrie 2022 17:46:41
Problema Teren Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>

#define MAXN 303

using namespace std;

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

int N, M, X, m[MAXN][MAXN], s[MAXN][MAXN];

int ans(int x, int y, int x1, int y1) {
    return s[x1][y1] - s[x - 1][y1] - s[x1][y - 1] + s[x - 1][y - 1];
}

int main()
{
    fin >> N >> M >> X;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            fin >> m[i][j];
        }
    }

    // construire sume partiale
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + m[i][j];
        }
    }

    int best = 0;
    for(int n = 1; n <= N; n++) {
        for(int m = 1; m <= M; m++) {

            for(int i = 1; i <= N - n + 1; i++) {
                for(int j = 1; j <= M - m + 1; j++) {
                    if(ans(i, j, i + n - 1, j + m - 1) <= X) {
                        best = max(best, n * m);
                    }
                }
            }

        }
    }

    fout << best;

    return 0;
}