Cod sursa(job #2854475)

Utilizator CosminDMRCosmin Damureanu CosminDMR Data 21 februarie 2022 14:06:01
Problema Teren Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
int sum[305][305], n, m, x, i, j, a, st, dr, i1, i2, s, Max = INT_MIN;
int main()
{
    ifstream in("teren.in");
    ofstream out("teren.out");
    in >> n >> m >> x;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            in >> a;
            sum[i][j] = sum[i-1][j] + a; /// suma tuturor elementelor din coloana j si liniile 1..i ///
        }
    for (i1 = 1; i1 <= n; i1++) /// linia de sus ///
        for (i2 = i1; i2 <= n; i2++)/// linia de jos ///
        {
            st = 1; /// coloana din stanga ///
            s = 0;
            for (dr = 1; dr <= n; dr++)
            {
                s += sum[i2][dr] - sum[i1-1][dr];
                while (st <= dr && s > x)
                {
                    s -= (sum[i2][st] - sum[i1-1][st]);
                    st++;
                }
                if ((i2 - i1 + 1) * (dr - st + 1) > Max)
                    Max = (i2 - i1 + 1) * (dr - st + 1);
            }
        }
    out << Max;
    return 0;
}