Pagini recente » Cod sursa (job #2713750) | Cod sursa (job #979605) | Cod sursa (job #2668121) | Cod sursa (job #1461975) | Cod sursa (job #2333657)
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
const int DN=305;
int m,n,l,u;
int R,C;
int st,dr,mij;
double sum[DN],val,sol,t;
int b[DN][DN];
pair<double,double>a[DN];
pair<double,int>d[DN];
int vf(double z)
{
for(int i=1;i<=n;i++)
{
val=a[i].x-a[i].y*z;
sum[i]=sum[i-1]+val;
}
int ds=1,dr=0;
for(int i=1;i<=n;i++)
{
if(i>=l)
{
while(1)
{
if(ds>dr)
break;
if(sum[i-l]>d[dr].x)
break;
dr--;
}
dr++;
d[dr]={sum[i-l],i};
}
if(ds<=dr)
if(sum[i]-d[ds].x>0)
return 1;
}
return 0;
}
int main()
{
fin>>m>>n;
fin>>R>>C;
if(R==0)
R=1;
if(C==0)
C=1;
l=C;
u=2*n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
fin>>b[i][j];
for(int i=1;i<=m;i++)
for(int j=n+1;j<=2*n;j++)
b[i][j]=b[i][j-n];
n*=2;
for(int i=m+1;i<=2*m;i++)
for(int j=1;j<=n;j++)
b[i][j]=b[i-m][j];
m*=2;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
b[i][j]+=b[i-1][j];
for(int i1=1;i1<=m/2;i1++)
for(int i2=i1+R-1;i2<=min(m,i1-1+m/2);i2++)
{
for(int i=1;i<=n;i++)
{
a[i].y=1;
a[i].x=b[i2][i]-b[i1-1][i];
a[i].x/=i2-i1+1;
}
st=sol*1000;
if(!vf(st))
continue;
dr=1e8;
while(st<dr)
{
mij=(st+dr+1)/2;
t=mij;
t/=1000;
if(vf(t))
st=mij;
else
dr=mij-1;
}
//st++;
t=st;
t/=1000;
if(vf(t+9e-4+9e-5+9e-6+9e-7))
t+=1e-3;
sol=max(sol,t);
}
fout<<fixed<<setprecision(3)<<sol;
}