Pagini recente » Cod sursa (job #855676) | Cod sursa (job #683262) | Cod sursa (job #809645) | Cod sursa (job #2101079) | Cod sursa (job #2350621)
#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;
}