Pagini recente » Cod sursa (job #1685830) | Cod sursa (job #1531997) | Cod sursa (job #1014246) | Cod sursa (job #3267589) | Cod sursa (job #1841845)
#include<bits/stdc++.h>
#define eps 0.001
using namespace std;
int n,m,r,c;
int a[305][305],v[305],sum[305][305],st,dr,mid,sol;
deque<int> q;
bool ok(int val)
{
for(int i=1;i<=n;i++)
{
for(int j=(i+r-1);j<=(i+n-1);j++)
{
for(int k=1;k<=(2*m);k++) v[k]=sum[j][k]-sum[i-1][k];
q.clear();
for(int k=1;k<=(2*m);k++) v[k]=v[k-1]+v[k];
int d=n-c+1;
for(int k=c;k<=(2*m);k++)
{
while(!q.empty() && v[k-c]<=v[q.back()]) q.pop_back();
q.push_back(k-c);
while(!q.empty() && q.front()<(k-m)) q.pop_front();
if((v[k]-v[q.front()])>=0) return 1;
}
}
}
return 0;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
a[i][j]*=1000;
a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
}
}
st=1;
dr=(1<<25);
while(st<=dr)
{
mid=(st+dr)/2;
for(int i=1;i<=(n<<1);i++)
{
for(int j=1;j<=(m<<1);j++) a[i][j]-=mid;
}
for(int i=1;i<=(2*n);i++)
{
for(int j=1;j<=(2*m);j++)
{
sum[i][j]=sum[i-1][j]+a[i][j];
}
}
if(ok(mid))
{
sol=mid;
st=mid+1;
}
else dr=mid-1;
for(int i=1;i<=(n<<1);i++)
{
for(int j=1;j<=(m<<1);j++) a[i][j]+=mid;
}
}
printf("%.3f\n",sol/1000.0);
return 0;
}