Pagini recente » Cod sursa (job #157433) | Cod sursa (job #2015212) | Cod sursa (job #2756940) | Profil Simon2712 | Cod sursa (job #1621373)
#include <cstdio>
#include <cstring>
FILE* in=fopen("balans.in","r");
FILE* out=fopen("balans.out","w");
const int Q=160;
int n,m,r,c;
int v[2*Q][2*Q];
int nrlin;
long long act[2*Q];
bool mergee(double r)
{
r*=nrlin;
double meu=0;
for(int i=1; i<=c; i++)
{
meu+=act[i]-r;
}
if(meu>=0)
return 1;
int st=1;
double befor=0;
for(int i=c+1; i<=2*m; i++)
{
while(i-st+1>m)
{
befor-=act[st]-r;
st++;
}
if(befor+act[i-c] > act[i-c])
befor+=act[i-c]-r;
else
{
befor=act[i-c]-r;
st=i-c;
}
if(befor<0)
{
befor=0;
st=i-c+1;
}
meu-=act[i-c]-r;
meu+=act[i]-r;
if(meu+befor>=0)
return 1;
}
return 0;
}
double ask()
{
double p=1<<17;
double rez=0;
for(int pas=1; pas<=30; pas++)
{
if(mergee(rez+p))
rez+=p;
p/=2;
}
return rez;
}
int main()
{
fscanf(in,"%d%d%d%d",&n,&m,&r,&c);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
fscanf(in,"%d",&v[i][j]);
v[i+n][j]=v[i][j];
v[i][j+m]=v[i][j];
v[i+n][j+m]=v[i][j];
}
}
double best=0;
double far;
for(nrlin=r; nrlin<=n; nrlin++)
{
memset(act,0,sizeof act);
for(int i=1; i<=2*m; i++)
{
for(int j=1; j<nrlin; j++)
{
act[i]+=v[j][i];
}
}
for(int i=nrlin; i<=2*n-nrlin+1; i++)
{
for(int j=1; j<=2*m; j++)
{
act[j]-=v[i-nrlin][j];
act[j]+=v[i][j];
}
far=ask();
if(far>best)
best=far;
}
}
fprintf(out,"%.4lf\n",best);
return 0;
}