Cod sursa(job #1601765)

Utilizator algebristulFilip Berila algebristul Data 16 februarie 2016 11:08:36
Problema Teren Scor 100
Compilator cpp Status done
Runda contest_3 Marime 1.02 kb
#include <cstdio>
#include <deque>

using namespace std;

const int nmax = 305;
int D[nmax][nmax];
int n, m, x;

bool ok(int x1, int y1, int x2, int y2) {
    int cnt = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
    return cnt <= x;
}

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

    scanf("%d %d %d", &n, &m, &x);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &D[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            D[i][j] += D[i][j-1] + D[i-1][j] - D[i-1][j-1];
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        for (int k = i; k <= n; k++) {
            int l, r;
            for (r = 1, l = 1; r <= m; r++) {
                while (!ok(i, l, k, r) && l <= r) {
                    l++;
                }

                ans = max(ans, (r - l + 1) * (k - i + 1));
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}