Pagini recente » Cod sursa (job #2710758) | Cod sursa (job #540649) | Cod sursa (job #832923) | Cod sursa (job #1078587) | Cod sursa (job #1497578)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 152
#define p10 1000
using namespace std;
int m, r, c, n, i, j, maxv, st, dr, d[maxN * 2];
int a[maxN * 2][maxN * 2], sum[maxN * 2][maxN * 2], s[maxN * 2][maxN * 2];
void read()
{
freopen("balans.in", "r", stdin);
scanf("%d %d %d %d", &n, &m, &r, &c);
for (i = 1; i <= n; ++ i)
{
for (j = 1; j <= m; ++ j)
{
scanf("%d", &a[i][j]);
a[i][j] *= p10;
a[i + n][j] = a[i][j];
if (a[i][j] > maxv)
maxv = a[i][j];
}
for (j = m + 1; j <= 2 * m; ++ j)
{
a[i][j] = a[i][j - m];
a[i + n][j] = a[i][j - m];
}
}
}
void right(int j)
{
while (st <= dr && s[i][j - c] <= s[i][d[dr]])
-- dr;
d[++ dr] = j - c;
}
void left(int j)
{
if (st <= dr && j - d[st] == n)
++ st;
}
int ok(int x)
{
int i, j, h;
memset(sum, 0, sizeof(sum));
for (h = r; h <= n; ++ h)
{
for (i = 1; i <= n * 2; ++ i)
for (j = 1; j <= 2 * m; ++ j)
{
sum[i][j] = sum[i - 1][j] + a[i][j] - x;
if (i >= h)
s[i][j] = s[i][j - 1] + sum[i][j] - sum[i - h][j];
}
for (i = h; i <= 2 * n; ++ i)
{
st = 1; dr = 0;
for (j = c; j <= m * 2; ++ j)
{
right(j);
left(j);
if (s[i][j] - s[i][d[st]] >= 0)
return 1;
}
for (j = 1; j <= 2 * m; ++ j)
s[i][j] = 0;
}
}
return 0;
}
int bs()
{
int i = 0, p = 1 << 26;
while (p)
{
if (i + p <= maxv && ok(i + p))
i += p;
p /= 2;
}
return i;
}
void write()
{
int x;
freopen("balans.out", "w", stdout);
x = bs();
double sol = (double)(x * 1.000 / 1000);
printf("%.3lf", sol * 1.000);
}
int main()
{
read();
write();
return 0;
}