Pagini recente » Cod sursa (job #210796) | Cod sursa (job #2563506) | Cod sursa (job #1490815) | Cod sursa (job #1868029) | Cod sursa (job #2448405)
#include<fstream>
#include<iomanip>
using namespace std;
ifstream cin("balans.in");
ofstream cout("balans.out");
int n,m,r,c,fr,bk;
int a[305][305],b[305][305],d[305];
long long s[305][305];
int le,ri;
inline long long dim(int i,int j,int k){
return s[j][k]-s[i-1][k];
}
long long maxsecv(int i,int j){
long long q=-1e13;
fr=1; bk=0;
for(int k=1;k<=r-1;k++){
while(fr<=bk && dim(i,j,d[bk])>=dim(i,j,k-1)) --bk;
d[++bk]=k-1;
}
for(int k=r;k<2*m;k++){
while(fr<=bk && dim(i,j,d[bk])>=dim(i,j,k-1)) --bk;
d[++bk]=k-1;
if(d[fr]==k-n-1) ++fr;
q=max(q,dim(i,j,k)-dim(i,j,d[fr]));
}
return q;
}
long long ans(int x){
for(int i=1;i<2*n;i++)
for(int j=1;j<2*m;j++)
b[i][j]=a[i][j]-x;
for(int i=1;i<2*n;i++)
for(int j=1;j<2*m;j++)
s[i][j]=b[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];
long long q=-1e13;
for(int i=1;i<=2*n-r;i++)
for(int j=i+r-1;j<=min(2*n-1,i+n-1);j++)
q=max(q,maxsecv(i,j));
return q;
}
int main(){
cin>>n>>m>>r>>c;
if(!r) r=1;
if(!c) c=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
a[i][j]*=1000;
}
for(int i=n+1;i<2*n;i++)
for(int j=1;j<=m;j++)
a[i][j]=a[i-n][j];
for(int i=1;i<2*n;i++)
for(int j=m+1;j<2*m;j++)
a[i][j]=a[i][j-m];
//for(int i=1;i<2*n;i++,cout<<'\n')
//for(int j=1;j<2*m;j++,cout<<' ')
// cout<<a[i][j];cout<<'\n';
le=0; ri=1e8;
while(ri-le>1){
int middle=(ri+le)/2;
if(ans(middle)>=0) le=middle;
else ri=middle;
//cout<<middle<<' '<<ans(middle)<<'\n';
}
// cout<<le<<' '<<ans(le)<<'\n';
if(ans(le)>=0) cout<<le/1000.0;
else cout<<ri/1000.0;
}