Pagini recente » Cod sursa (job #1594601) | Cod sursa (job #327456) | Cod sursa (job #1842575) | Cod sursa (job #978789) | Cod sursa (job #850451)
Cod sursa(job #850451)
#include<stdio.h>
#include<string.h>
int n,m,r,c,a[305][305];
int d[305][305];
int v[305],deque[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,p,u;
touch(-x); memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
d[i][j]=d[i-1][j]+a[i][j];
for(i1=1;i1<=n/2;i1++)
for(i2=i1+r-1;i2<=n;i2++)
{
if(i2-i1+1>n/2) break;
for(j=1;j<=m;j++)
v[j]=v[j-1] + (d[i2][j]-d[i1-1][j]);
p=1;u=0;memset(deque,0,sizeof(deque));
for(j=c+1;j<=m;j++)
{
deque[++u]=j-c;
while(v[deque[u]] < v[deque[u-1]] && u>p)
{
deque[u-1]=deque[u];deque[u]=0;
u--;
}
while(deque[p]<j-m/2+1 && p<u) p++;
if(v[j]>=v[deque[p]]) {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]=1000*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/1000;
printf("%.3lf\n",ans-0.000499);
return 0;
}