Pagini recente » Cod sursa (job #2382915) | Cod sursa (job #3126234) | Cod sursa (job #2120660) | Cod sursa (job #895468) | Cod sursa (job #1205144)
#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;
const int BufferSize = 8000000;
char Buffer[BufferSize];
int BufferCursor;
void Read(int &N)
{
N = 0;
while (Buffer[BufferCursor] >= '0' && Buffer[BufferCursor] <= '9')
{
N = 10 * N + Buffer[BufferCursor] - '0';
BufferCursor++;
if (BufferCursor == BufferSize)
{
BufferCursor = 0;
fread(Buffer, 1, BufferSize, stdin);
}
}
BufferCursor++;
if (BufferCursor == BufferSize)
{
BufferCursor = 0;
fread(Buffer, 1, BufferSize, stdin);
}
}
const int Nmax = 155;
int Values[2 * Nmax][2 * Nmax];
long long SumC[2 * Nmax][2 * Nmax];
int N, M, R, C;
bool Check(const long long t)
{
const int N1 = N, M1 = M, N2 = 2 * N, M2 = 2 * M, RR = R, CC = C;
vector<long long> SumL(M2 + 1, 0);
for (int up = 0; up + RR <= N2; up++)
{
for (int down = up + RR; down <= N2 && down - up <= N1; down++)
{
for (int i = 1; i <= M2; i++)
SumL[i] = SumL[i - 1] + SumC[down][i] - SumC[up][i] - t * (down - up);
deque<int> D;
for (int i = CC; i <= M2; i++)
{
while (!D.empty() && SumL[i - CC] <= SumL[D.back()]) D.pop_back();
D.push_back(i - CC);
while (!D.empty() && i - D.front() > M1) D.pop_front();
if (!D.empty() && SumL[i] - SumL[D.front()] >= 0) return 1;
}
}
}
return 0;
}
int main()
{
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
fread(Buffer, 1, BufferSize, stdin);
Read(N); Read(M); Read(R); Read(C);
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
Read(Values[i][j]);
Values[i][j] *= 1000;
Values[i + N][j] = Values[i][j + M] = Values[i + N][j + M] = Values[i][j];
}
}
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 l = 0, r = 100000000, Sol = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (Check(mid))
{
Sol = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%d.%d\n", Sol / 1000, Sol % 1000);
}