Pagini recente » Cod sursa (job #1240194) | Cod sursa (job #318952) | Cod sursa (job #3177807) | Cod sursa (job #2312010) | Cod sursa (job #850426)
Cod sursa(job #850426)
#include<stdio.h>
#include<string.h>
int n,m,r,c,a[305][305];
int d[305][305];
inline int min(int a,int b) {return a>b?b:a;}
inline void touch(int x) {int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]+=x;}
bool good(int x)
{
int i1,i2,i,j,j1,j2;
touch(-x); memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
d[i][j]=a[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
for(i1=1;i1<=n;i1++)
for(i2=i1+r-1;i2<=min(i1+n/2-1,n);i2++)
for(j1=1;j1<=m;j1++)
for(j2=j1+c-1;j2<=min(m,j1+m/2-1);j2++)
if(d[i2][j2]+d[i1-1][j1-1]-d[i1-1][j2]-d[i2][j1-1]>=0)
{
touch(x);
return true;
}
touch(x); return false;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
int i,j,max=0;
scanf("%d%d%d%d",&n,&m,&r,&c);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);a[i][j]=10000*a[i][j];
a[n+i][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
if(a[i][j]>max) max=a[i][j];
}
n=2*n;m=2*m;
int st,dr,med,last;
st=0;dr=max;last=0;
while(st<=dr)
{
med=(st+dr)/2;
if(good(med))
{
last=med;
st=med+1;
}
else
dr=med-1;
}
double ans;
ans=(double)last/10000;
printf("%.3lf\n",ans-0.000499);
return 0;
}