Pagini recente » Cod sursa (job #1574794) | Cod sursa (job #262051) | Cod sursa (job #1686175) | Cod sursa (job #1176842) | Cod sursa (job #390838)
Cod sursa(job #390838)
#include<fstream.h>
#define VMAX 300
int m,n,X,maxim,apel=1,lin[VMAX][VMAX];
unsigned char mat[VMAX][VMAX];
void read()
{
ifstream f("teren.in");
f>>n>>m>>X;
int i,j,var;
int v[VMAX];
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
{ f>>var;
if(i==0)v[j]=0;
v[j]+=var;
lin[i][j]=v[j];
if(j>0)lin[i][j]+=lin[i][j-1];
}
}
f.close();
}
int suma(int x1,int y1,int x2,int y2)
{
int i=0,s;
s=lin[x2][y2];
if(y1>0){s-=lin[x2][y1-1];i=1;}
if(x1>0)
{
if(i)s-=(lin[x1-1][y2]-lin[x1-1][y1-1]);
else s-=lin[x1-1][y2];
}
return s;
}
void search(int x,int y)
{
int i=x,j=y,var,s=0;
while(i>=x)
{
var=(i-x+1)*(j-y+1);
s=0;
while(var<=maxim&&s!=X+1&&suma(x,y,i,j)<=X)
{
if(mat[i][j]!=apel)mat[i][j]=apel;
else s=X+1;
if(mat[i+1][j]!=apel)++i;
else ++j;
if(i==n)
{--i;++j;}
if(j>=m)
{--j;}
var=(i-x+1)*(j-y+1);
}
s=suma(x,y,i,j);
if(mat[i][j]!=apel)mat[i][j]=apel;
else s=X+1;
if(s<=X&&j<m&&i<n)
{
if(var>maxim)maxim=var;
if(mat[i+1][j]!=apel)++i;
else ++j;
}
else
{
--i;
if((i-x+1)*(m-y)<=maxim)
return;
if(mat[i][j]==apel)++j;
}
if(i==n)
{--i;++j;}
if(j>=m)
{--j;}
}
}
int solve()
{
int i,j,var;
maxim=0;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
if((n-i)*(m-j)>maxim){search(i,j);++apel;}
return maxim;
}
int main()
{
read();
ofstream g("teren.out");
g<<solve();
g.close();
return 0;
}