Pagini recente » Cod sursa (job #346535) | Cod sursa (job #1810184) | Cod sursa (job #985914) | Cod sursa (job #262063) | Cod sursa (job #1205147)
#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;
const int Nmax = 155;
const double EPS = 1e-8;
int Values[2 * Nmax][2 * Nmax], SumC[2 * Nmax][2 * Nmax];
double SumL[2 * Nmax];
int N, M, R, C;
bool Check(const double t)
{
for (int up = 0; up <= N; up++)
{
for (int down = up + R; down - up <= N; down++)
{
for (int i = 1; i <= 2 * M; i++)
SumL[i] = SumL[i - 1] + SumC[down][i] - SumC[up][i] - t * (down - up);
deque<int> D;
for (int i = C; i <= 2 * M; i++)
{
while (!D.empty() && SumL[i - C] <= SumL[D.back()]) D.pop_back();
D.push_back(i - C);
while (!D.empty() && i - D.front() > M) D.pop_front();
if (SumL[i] - SumL[D.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("%d", &Values[i][j]);
for (int i = N + 1; i <= 2 * N; i++)
for (int j = 1; j <= M; j++)
Values[i][j] = Values[i - N][j];
for (int i = 1; i <= 2 * N; i++)
for (int j = M + 1; j <= 2 * M; j++)
Values[i][j] = Values[i][j - M];
for (int i = 1; i <= 2 * N; i++)
for (int j = 1; j <= 2 * M; j++)
SumC[i][j] = SumC[i - 1][j] + Values[i][j];
int Sol = 0;
for (int step = (1 << 26); step; step >>= 1)
{
if (Check((Sol | step) / 1000.0))
Sol |= step;
}
printf("%d.%d\n", Sol / 1000, Sol % 1000);
}