Pagini recente » Cod sursa (job #1251731) | Cod sursa (job #3243363) | Cod sursa (job #2953722) | Cod sursa (job #2567047) | Cod sursa (job #1672731)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
const int Mn = 400;
int n, m, r, c;
ll ans;
ll ar[Mn][Mn], sm[Mn][Mn], row[Mn];
bool ok(ll x)
{
for (int i = 0; i <= n / 2; i++)
for (int j = i + r; j - i <= n / 2; j++)
{
for (int it = 1; it <= m; it++)
row[it] = row[it - 1] + sm[j][it] - sm[i][it] - 1LL * x * (j - i);
deque< ll > dq;
for (int it = c; it <= m; it++)
{
while (!dq.empty() && row[dq.back()] >= row[it - c])
dq.pop_back();
dq.push_back(it - c);
while (!dq.empty() && it - dq.front() > m / 2)
dq.pop_front();
if (row[it] - row[dq.front()] >= 0)
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 (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%lld", &ar[i][j]), ar[i + n][j] = ar[i][j + m] = ar[i + n][j + m] = ar[i][j];
n *= 2;
m *= 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ar[i][j] *= 1000, sm[i][j] = sm[i - 1][j] + ar[i][j];
for (int it = (1 << 20); it; it /= 2)
if (ok(ans + it))
ans += it;
printf("%lld.%lld\n", ans / 1000, ans % 1000);
return 0;
}