Cod sursa(job #3036357)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 24 martie 2023 11:12:36
Problema Teren Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <cmath>

using namespace std;

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

int n, m, x, st, dr, mid, sol;
int teren[301][301];
bool tipTeren;

int Check(int lin, int col)
{
    bool posibil = false;
    if(lin <= n && col <= m)
    {
        for(int j = lin; j <= n; j++)
        {
            for(int k = col; k <= m; k++)
            {
                int terenProst = teren[j][k] - teren[j - lin][k] - teren[j][k - col] + teren[j - lin][k - col];
                if(terenProst <= x)
                {
                    posibil = true;
                    break;
                }
            }
            if(posibil)
                break;
        }
    }
    return posibil;
}

int main()
{
    fin >> n >> m >> x;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            fin >> tipTeren;
            teren[i][j] = teren[i - 1][j] + teren[i][j - 1] - teren[i - 1][j - 1] + tipTeren;
        }
    }
    st = 1;
    dr = n * m;
    while(st <= dr)
    {
        bool posibil = false;
        mid = (st + dr) / 2;
        for(int i = 1; i <= sqrt(mid); i++)
        {
            if(posibil)
                break;
            if(mid % i == 0)
            {
                int lin = i;
                int col = mid / i;
                posibil = Check(lin, col);
                if(posibil)
                    break;
                swap(lin, col);
                posibil = Check(lin, col);
            }
        }
        if(posibil)
        {
            st = mid + 1;
            sol = mid;
        }
        else
        {
            dr = mid - 1;
        }
    }
    fout << sol;
}