Cod sursa(job #2413322)

Utilizator osiaccrCristian Osiac osiaccr Data 23 aprilie 2019 12:07:58
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 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; ++ lin1) {
        for (int lin2 = lin1; lin2 <= n; ++ lin2) {
            int st = 1, sum = 0;

            for (int dr = 1; dr <= m; ++ dr) {
                sum += M[lin2][dr] - M[lin1 - 1][dr];

                while (sum > maxSum and st <= dr) {
                    sum -= M[lin2][st] - M[lin1 - 1][st];
                    ++ st;
                }

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

        }
    }

    fout << maxArea;

    return 0;
}