Pagini recente » Cod sursa (job #848422) | Cod sursa (job #443521) | Cod sursa (job #2624044) | Cod sursa (job #2028024) | Cod sursa (job #1751176)
#include <iostream>
#include <cstdio>
#define MAXN 164
#define MAXM 164
using namespace std;
int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN];
int n, m, r, c;
void citire()
{
scanf("%d %d %d %d", &n, &m, &r, &c);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
a[i][j+m] = a[i+n][j] = a[i+n][j+m] = a[i][j];
}
for (int i = 1; i <= 2*n; i++)
for (int j = 1; j <= 2*m; j++)
pre[i][j] = pre[i-1][j] + a[i][j];
}
int check(int stx, int len, double k)
{
double crt[2*MAXM];
int deck[2*MAXM];
crt[0] = 0;
for (int i = 1; i <= m; i++)
crt[i] = crt[i-1] + pre[stx+len-1][i] - pre[stx-1][i] - (k*len);
double val = 0;
if (crt[c] > 0) return 1;
int st = 0, dr = -1;
for (int i = c+1; i <= m; i++) {
while (st <= dr && crt[i-c] < crt[deck[dr]])
dr--;
deck[++dr] = i-c;
while (i-deck[st] > m)
st++;
double scad = crt[deck[st]];
if (crt[i]-scad >= 0) return 1;
}
return 0;
}
void solve()
{
double rez = -1;
for (int i = 1; i <= 2*n-r+1; i++)
for (int j = r; i+j-1 <= 2*n; j++) {
double k, lo = 0, hi = 1000000;
while (hi - lo > 0.00008) {
k = (lo + hi) / 2;
if (check(i, j, k))
lo = k;
else
hi = k;
}
if (lo > rez)
rez = lo;
}
printf("%.3lf", rez);
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
citire();
solve();
return 0;
}