Pagini recente » Cod sursa (job #2290523) | Cod sursa (job #1064315) | Cod sursa (job #1197900) | Cod sursa (job #1000304) | Cod sursa (job #480993)
Cod sursa(job #480993)
#include <stdio.h>
#define Nmax 155*2
#define CT 1000
#define LL long long
using namespace std;
int Deq[Nmax];
int a[Nmax][Nmax]; LL Sc[Nmax][Nmax];
LL Sum[Nmax];
int N,M,R,C;
inline LL Maxim(LL x,LL y){ return x>y ? x:y; }
inline LL Minim(LL x,LL y){ return x<y ? x:y; }
int bun(LL X){
int i,i2,j,q,p,u; LL mx,sum_ac;
for(i=1;i<=2*N;++i)
for(j=1;j<=2*M;++j)
Sc[i][j]=Sc[i-1][j]+(LL)(a[i][j]-X);
for(i=1; i<=2*N-R+1; ++i)
for(i2=i+R-1, q=Minim(2*N,i+N-1); i2<=q; ++i2){
p=1; u=0;
Deq[1]=1;
for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j];
mx = Sum[C];
for(j=C+1; j<=2*M; ++j){
while( Deq[p]+M-1 < j )
p++;
sum_ac=Sum[j]-Sum[j-C];
while( u>=p && Sum[j]-Sum[Deq[u]-1] < sum_ac )
u--;
Deq[++u]=j-C+1;
mx=Maxim(mx,Sum[j]-Sum[Deq[p]-1]);
}
if( mx >= 0 )
return 1;
}
return 0;
}
int main(){
int i,j, Max=0,l,r,m,rez;
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
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]*=CT;
a[i+N][j]=a[i][j+M]=a[i+N][j+M]=a[i][j];
Max=Maxim(a[i][j],Max);
}
for(l=0, r=Max; l<=r; ){
m=l+(r-l)/2;
if( bun(m) ){
rez=m;
l=m+1;
}
else r=m-1;
}
printf("%.3lf\n",(rez*1.0/CT));
fclose(stdin); fclose(stdout);
return 0;
}