Pagini recente » Cod sursa (job #159498) | Cod sursa (job #2365167) | Cod sursa (job #2027913) | Cod sursa (job #1682573) | Cod sursa (job #3036357)
#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;
}