Pagini recente » Cod sursa (job #1859088) | Cod sursa (job #686227) | Cod sursa (job #1486411) | Cod sursa (job #158179) | Cod sursa (job #934411)
Cod sursa(job #934411)
#include <cstdio>
#include <iostream>
using namespace std;
const int max_n=305;
const double EPS=0.00000001;
int El[max_n][max_n];
int n,m,R,C;
int i,j;
bool bs( double rez ){
double SP[max_n][max_n];
int Deq[max_n];
int i,j,l1,l2,c,st,dr;
for( i=0; i<max_n; ++i )
SP[i][0]=SP[0][i]=0.0;
for( i=1; i<=n; ++i )
for( j=1; j<=m; ++j ){
SP[i][j] = SP[i][j-1] + SP[i-1][j] - SP[i-1][j-1] + El[i][j] - rez;
}
for( l1=1; l1<=n; ++l1 )
for( l2=l1+R-1; l2<=n; ++l2 ){
// calculam de la 0
dr=0;
st=1;
for( c=C; c<=m; ++c ){
// introducem coloana c-C/
while( dr && ( SP[l2][c-C] - SP[l1-1][c-C] - SP[l2][Deq[dr]] + SP[l1-1][Deq[dr]] < EPS ) )
dr--;
Deq[++dr]=c-C;
if( Deq[st] == c-m/2 )
++st;
if( SP[l2][c] - SP[l1-1][c] - SP[l2][ Deq[st] ] + SP[l1-1][ Deq[st] ] > 0 ){
return true;
}
}
}
return false;
}
int main(){
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", &El[i][j] );
El[i+n][j]=El[i][j];
El[i][j+m]=El[i][j];
El[i+n][j+m]=El[i][j];
}
n*=2;
m*=2;
double rez=0.0, p=(1<<20)*1.0;
int target=35;
for( ; target; target--, p/=2.0 )
if( bs( rez+p ) )
rez+=p;
printf("%.3lf", rez);
return 0;
}