Pagini recente » Cod sursa (job #2958116) | Cod sursa (job #67593) | Cod sursa (job #2252223) | Cod sursa (job #2830460) | Cod sursa (job #1497596)
#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];
a[i][j + m] = a[i][j];
a[i + n][j + m] = a[i][j];
}
}
}
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 && d[st] < j - m)
++ st;
}
int ok(int x)
{
int i, j, h;
memset(sum, 0, sizeof(sum));
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;
for (h = r; h <= n; ++ h)
{
memset(s, 0, sizeof(s));
for (i = h; i <= n * 2; ++ i)
for (j = 1; j <= 2 * m; ++ j)
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;
}
}
}
return 0;
}
int bs()
{
int i = 0, p = 1 << 27;
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)((double)(x * 1.000) / 1000.000);
printf("%.3lf", sol * 1.000);
}
int main()
{
read();
write();
return 0;
}