Cod sursa(job #2413313)

Utilizator osiaccrCristian Osiac osiaccr Data 23 aprilie 2019 11:56:51
Problema Teren Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define DEF 310

using namespace std;

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

int n, m, maxSum, maxArea, M[DEF][DEF];

int main () {

    fin >> n >> m >> maxSum;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            int x;
            fin >> x;
            M[i][j] = M[i - 1][j] + x;
        }
    }

    for (int lin1 = 1; lin1 <= n - 1; ++ lin1) {
        for (int lin2 = lin1 + 1; lin2 <= n; ++ lin2) {
            int st = 1, dr = 1, sum = M[lin2][1] - M[lin1 - 1][1];
            for (; dr <= m; ++ dr) {
                sum += M[lin2][dr] - M[lin1 - 1][dr];
                while (sum > maxSum) {
                    sum -= M[lin2][st] - M[lin1 - 1][st];
                    ++ st;
                }

                if ((lin2 - lin1 + 1) * (dr - st + 1) > maxArea) {
                    maxArea = (lin2 - lin1 + 1) * (dr - st + 1);
                }
            }

        }
    }

    fout << maxArea;

    return 0;
}