Pagini recente » Cod sursa (job #1946909) | Cod sursa (job #1620750) | Cod sursa (job #721122) | Cod sursa (job #1706015) | Cod sursa (job #1843171)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 303;
int N, M, R, C, i, j, st, dr, mid;
long long a[Nmax][Nmax], b[Nmax];
bool good()
{
int i, p1=1, p2=0, dq[Nmax];
for(i=C; i<=2*M; ++i)
{
if(p1<=p2 && dq[p1]==i-M-1) ++p1;
while(p1<=p2 && b[dq[p2]] >= b[i-C]) --p2;
dq[++p2] = i-C;
if(b[i] >= b[dq[p1]]) return 1;
}
return 0;
}
bool check(int x)
{
int i, j, k;
for(i=1; i<=2*N; ++i)
for(j=i+R-1; j<=i+N-1 && j<=2*N; ++j)
{
for(k=1; k<=2*M; ++k)
b[k] = b[k-1] + a[j][k] - a[i-1][k] - 1LL*x*(j-i+1);
if(good()) return 1;
}
return 0;
}
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", &a[i][j]);
for(i=1; i<=2*N; ++i)
for(j=1; j<=2*M; ++j)
a[i][j] = a[i<=N ? i : i-N][j<=M ? j : j-M];
for(i=1; i<=2*N; ++i)
for(j=1; j<=2*M; ++j)
a[i][j] = a[i-1][j] + 1000*a[i][j];
st=0; dr=1e8;
while(st<=dr)
{
mid = (st+dr)/2;
if(check(mid)) st = mid+1;
else dr = mid-1;
}
printf("%.3lf\n", (double)dr/1000);
return 0;
}