Cod sursa(job #2350624)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 21 februarie 2019 16:37:46
Problema Teren Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>

using namespace std;

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

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

int calc(int lgLin, int lgCol)
{
    int rez = 0;
    if(lgLin == 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;
                }
            }
        }
    }
    else
    {
        for(int i = lgLin; i <= m; ++i)
        {
            int p1 = 1;
            int p2 = 1;
            while(p2 <= n)
            {
                int s = sum[p2][i] - sum[p1 - 1][i] - sum[p2][i - lgLin] + sum[p1 - 1][i - lgLin];
                if(s > x)
                {
                    if(p1 == p2)
                        ++p2;
                    else ++p1;
                }
                else
                {
                    rez = max(rez, (lgLin * (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)
        {
            fin >> mat[i][j];
            sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }

    int st = 1;
    int dr = n;
    int ArieMaxim = 0;
    while(st <= dr)
    {
        int lgCol = (st + dr) / 2;
        int arie = calc(0, lgCol);
        if(arie > ArieMaxim)
        {
            ArieMaxim = arie;
            st = lgCol + 1;
        }
        else
            dr = lgCol - 1;
    }

    st = 1;
    dr = m;
    while(st <= dr)
    {
        int lgLin = (st + dr) / 2;
        int arie = calc(lgLin, 0);

        if(arie > ArieMaxim)
        {
            ArieMaxim = arie;
            st = lgLin + 1;
        }
        else
            dr = lgLin - 1;
    }

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