Pagini recente » Cod sursa (job #1075481) | Cod sursa (job #2519812) | Cod sursa (job #11565) | Cod sursa (job #154705) | Cod sursa (job #1843166)
#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()
{
deque<int> dq;
int i;
for(i=C; i<=2*M; ++i)
{
if(dq.size() && dq.front()==i-M-1) dq.pop_front();
while(dq.size() && b[dq.back()] >= b[i-C]) dq.pop_back();
dq.push_back(i-C);
if(b[i] - b[dq.front()] >= 0) 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;
}