Pagini recente » Cod sursa (job #901125) | Cod sursa (job #639642) | Cod sursa (job #1537169) | Cod sursa (job #912338) | Cod sursa (job #801773)
Cod sursa(job #801773)
#include <iostream>
#include <iomanip>
#include <fstream>
#define DN 305
using namespace std;
int n,m,r,c,mc[DN][DN],sc[DN][DN],N,M,dq[DN],st,dr;
double v[DN];
bool check(int i1, int i2, double x) {
for(int i=1; i<=m; ++i) v[i]=sc[i2][i]-sc[i1-1][i]-x*(i2-i1+1)+v[i-1];
if(v[c]>=0) return 1;
st=0,dr=-1;
for(int i=c+1; i<=m; ++i) {
for(;st<=dr && v[dq[dr]]>=v[i-c]; --dr);
dq[++dr]=i-c;
for(;i-dq[st]+1>M; ++st);
if(v[i]-v[dq[st]]>=0) return 1;
}
return 0;
}
int main()
{
ifstream f("balans.in");
ofstream g("balans.out");
f>>n>>m>>r>>c;
N=n; M=m;
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) {
f>>mc[i][j];
mc[i+n][j]=mc[i][j+m]=mc[i+n][j+m]=mc[i][j];
}
n<<=1; m<<=1;
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) sc[i][j]=sc[i-1][j]+mc[i][j];
double rez=0;
for(int i1=1; i1<=N; ++i1) for(int i2=i1+r-1; i2<=n; ++i2) {
double ls=1,ld=10000000000,m;
for(int i=1; i<=64; ++i) {
m=(ls+ld)*0.5;
if(check(i1,i2,m)) ls=m;
else ld=m;
}
rez=max(rez,ls);
}
g<<fixed<<setprecision(3)<<rez;
return 0;
}