Pagini recente » Cod sursa (job #80583) | Cod sursa (job #169558) | Cod sursa (job #2373213) | Cod sursa (job #1902820) | Cod sursa (job #630341)
Cod sursa(job #630341)
#include <cstring>
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <deque>
using namespace std;
const int SIZE = 301;
const double eps = 0.000001;
int N, M, R, C;
int A[SIZE][SIZE];
double S[SIZE][SIZE];
deque<int> Dq;
inline double getsum(int i1, int j1, int i2, int j2)
{
return S[i2][j2] - S[i2][j1 - 1] - S[i1 - 1][j2] + S[i1 - 1][j1 - 1];
}
bool canget(double X)
{
memset(S, 0, sizeof(S));
for (int i = 1; i <= N * 2; ++i)
for (int j = 1; j <= M * 2; ++j)
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (1.0 * A[i][j] - X);
double resnow = -100000;
for (int i = 1; i <= N * 2 - R + 1; ++i)
for (int j = i + R - 1; j <= N * 2; ++j)
{
Dq.clear();
for (int k = C; k <= M * 2; ++k)
{
while (!Dq.empty() && Dq.front() < k - M)
Dq.pop_front();
while (!Dq.empty() && getsum(i, 1, j, k - C) < getsum(i, 1, j, Dq.back()))
Dq.pop_back();
Dq.push_back(k - C);
resnow = max(resnow, getsum(i, 1, j, k) - getsum(i, 1, j, Dq.front()));
}
}
return (resnow > 0);
}
int main()
{
ifstream fin("balans.in");
ofstream fout("balans.out");
fin >> N >> M >> R >> C;
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= M; ++j)
fin >> A[i][j];
for (int j = M + 1; j <= 2 * M; ++j)
A[i][j] = A[i][j - M];
}
for (int i = N + 1; i <= 2 * N; ++i)
for (int j = 1; j <= 2 * M; ++j)
A[i][j] = A[i - N][j];
double left = 0, right = 100000;
while (right - left > eps)
{
double mid = (left + right) / 2;
if (canget(mid)) left = mid;
else right = mid;
}
fout << fixed << setprecision(3) << left;
fin.close();
fout.close();
}