Cod sursa(job #2805903)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 22 noiembrie 2021 08:49:32
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define DIM 305

using namespace std;

ifstream f("teren.in");
ofstream g("teren.out");

int n, m, x, dp[DIM][DIM], maxi;

int main()
{
    f >> n >> m >> x;

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

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int first = 1, bad = 0;
            for (int k = 1; k <= m; k++)
            {
                bad += dp[j][k] - dp[i - 1][k];
                while (bad > x && first <= k)
                {
                    bad -= dp[j][first] - dp[i - 1][first];
                    first++;
                }

                if ((j - i + 1) * (k - first + 1) > maxi)
                {
                    ///g << j - i + 1 << " " << k - first + 1 << "\n";
                    maxi = (j - i + 1) * (k - first + 1);
                }

            }
        }
    }

    g << maxi;

    return 0;
}