Pagini recente » Cod sursa (job #2456885) | Cod sursa (job #2617544) | Cod sursa (job #2603048) | Cod sursa (job #1443957) | Cod sursa (job #480971)
Cod sursa(job #480971)
#include <stdio.h>
#include <deque>
#define Nmax 155*2
#define CT 1000
using namespace std;
deque< int > Deq;
int a[Nmax][Nmax],b[Nmax][Nmax],Sc[Nmax][Nmax];
int Sum[Nmax];
int N,M,R,C;
inline int Maxim(int x,int y){ return x>y ? x:y; }
inline int Minim(int x,int y){ return x<y ? x:y; }
int bun(int X){
int i,i2,j,mx,sum_ac;
for(i=1;i<=2*N;++i)
for(j=1;j<=2*M;++j){
b[i][j] = a[i][j]-X;
Sc[i][j]=Sc[i-1][j]+b[i][j];
}
for(i=1; i<=2*N-R+1; ++i)
for(i2=i+R-1; i2<=Minim(2*N,i+N-1); ++i2){
while( ! Deq.empty() )Deq.pop_back();
for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j];
Deq.push_back(1);
mx = Sum[C];
for(j=C+1; j<=2*M; ++j){
while( !Deq.empty() && Deq.front()+M-1 < j )
Deq.pop_front();
sum_ac=Sum[j]-Sum[j-C];
while( !Deq.empty() && Sum[j]-Sum[Deq.back()-1] < sum_ac )
Deq.pop_back();
Deq.push_back(j-C+1);
mx=Maxim(mx,Sum[j]-Sum[Deq.front()-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;
b[i][j]=b[i+N][j]=b[i][j+M]=b[i+N][j+M]=a[i][j];
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;
}