Cod sursa(job #2350652)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 21 februarie 2019 17:01:22
Problema Teren Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 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 ArieMaxim = 0;
    for(int i = 1; i <= n; ++i){
        ArieMaxim = max(calc(0, i), ArieMaxim);
    }

    int ArieMax2 = 0;
    for(int i = 1; i <= m; ++i){
        ArieMax2 = max(calc(i, 0), ArieMax2);
    }

    fout << max(ArieMaxim, ArieMax2) << '\n';
    return 0;
}