Pagini recente » Cod sursa (job #267226) | Cod sursa (job #240390) | Cod sursa (job #2255830) | Cod sursa (job #2840136) | Cod sursa (job #803947)
Cod sursa(job #803947)
#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
#define prec (1<<14)
#define max_n 305
#define calc(x) (Sp[j][x]-Sp[i-1][x])
int n,m,r,c;
int i,j;
long long El[max_n][max_n];
long long Sp[max_n][max_n];
deque<int> Deq;
bool solve ( long long Me ){
int i,j,k;
for ( i=1; i<=n; i++ ){
for ( j=1; j<=m; j++ ){
Sp[i][j]= (long long) Sp[i-1][j] + Sp[i][j-1] - Sp[i-1][j-1] +El[i][j] - Me;
}
}
long long act;
for ( i=1; i<=n/2; i++ ){
for ( j=i+r-1; ( j<i+n/2-1); j++ ){
act=0;
Deq.clear();
// initializam "suma"
Deq.push_back(0);
for ( k=c; k<=m; k++ ){
// adaugam coloana actuala.
act=calc(k);
if ( act - calc(Deq.front() )>= 0 ){
return 1;
}
// scoatem din Deq.
while ( !Deq.empty() && ( calc(k-c+1) < calc ( Deq.back() ) ) )
Deq.pop_back();
Deq.push_back(k-c+1);
if ( Deq.front() == k-(m/2)+1 )
Deq.pop_front();
}
}
}
return 0;
}
float CB (){
long long rez=0,ind=(long long)(1<<20)*prec;
for ( ; ind; ind>>=1 ){
if ( solve ( rez+ind ) ){
rez+=ind;
}
}
return (float)(1.0*rez/prec);
}
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 ("%lld", &El[i][j] );
El[i][j]*=prec;
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;
printf("%.3f", CB() );
return 0;
}