Pagini recente » Cod sursa (job #2768638) | Cod sursa (job #896864) | Cod sursa (job #1746376) | Cod sursa (job #686548) | Cod sursa (job #1723957)
#include<cstdio>
#include<algorithm>
#define MAXN 160
using namespace std;
int a[2*MAXN][2*MAXN],n,m,r,c;
long long sum[2*MAXN][2*MAXN];
long long v[2*MAXN];
int Deque[MAXN];
bool Check(long long value){
int i1,i2,j,left,right;
long long best;
for(i1=1;i1<=n;i1++)
for(i2=i1+r-1;i2<=i1+n-1;i2++){
for(j=1;j<=2*m;j++)
v[j]=v[j-1]+sum[i2][j]-sum[i1-1][j]-value*(i2-i1+1);
Deque[1]=1;
left=1;
right=0;
best=v[c];
for(j=c+1;j<=2*m&&Deque[left]<=m;j++){
while(left<=right&&Deque[left]+m-1<j)
left++;
while(left<=right&&v[Deque[right]-1]>=v[j-c])
right--;
left++;
Deque[left]=j-c+1;
best=max(best,v[j]-v[Deque[left]-1]);
}
if(best>=0)
return true;
}
return false;
}
int main(){
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
int i,j,left=0,right=0,middle,answer;
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+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
right=max(right,a[i][j]);
}
for(i=1;i<=2*n;i++)
for(j=1;j<=2*m;j++)
sum[i][j]=sum[i-1][j]+a[i][j];
while(left<=right){
middle=(left+right)/2;
if(Check(middle)==true){
answer=middle;
left=middle+1;
}
else
right=middle-1;
}
printf("%.3f",1.0*answer/1000);
return 0;
}