Cod sursa(job #2350658)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 21 februarie 2019 17:08:56
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;

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

int sum[305][305], n, m, x;

int calc(int lgCol)
{
    int rez = 0;

    for(int j = lgCol; j <= n; ++j)
    {
        int p1 = 1;
        int p2 = 1;
        while(p2 <= m)
        {
            int s = sum[j][p2] - sum[j][p1 - 1] - sum[j - lgCol][p2] + sum[j - lgCol][p1 - 1];
            if(s > x)
            {
                if(p1 == p2)
                    ++p2;
                else ++p1;
            }
            else
            {
                rez = max(rez, (lgCol * (p2 - p1 + 1)));
                ++p2;
            }
        }
    }
    return rez;
}

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

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

    int ArieMaxim = 0;
    for(int i = 1; i <= n; ++i)
        ArieMaxim = max(calc(i), ArieMaxim);

    fout << ArieMaxim << '\n';
    return 0;
}