Pagini recente » Cod sursa (job #882592) | Cod sursa (job #2296261) | Cod sursa (job #721377) | Cod sursa (job #2803363) | Cod sursa (job #946954)
Cod sursa(job #946954)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
#define rep(i, st, fn) for(int (i) = (st); (i) <= (fn); ++(i))
#define ll long long
const int MAXN = 310;
const int INF = 100000 * 1000;
int N, M, R, C;
int a[MAXN][MAXN],
ll sumR[MAXN][MAXN], sumC[MAXN];
deque<int> dq;
void insert_deque(int elem) {
while (!dq.empty() && sumC[dq.back()] > sumC[elem])
dq.pop_back();
dq.push_back(elem);
}
int get_deque(int limit) {
while (!dq.empty() && dq.front() < limit)
dq.pop_front();
return dq.front();
}
bool solve(int mid) {
for (int i = 1; i <= 2 * N; ++i)
for (int j = i + R - 1; j - i < N && j <= 2 * N; ++j) {
dq.clear();
rep(k, 1, 2 * M)
sumC[k] = sumC[k - 1] + (sumR[j][k] - sumR[i - 1][k] - 1LL * mid * (j - i + 1));
rep(k, C, 2 * M) {
insert_deque(k - C);
if (sumC[k] - sumC[get_deque(k - M)] >= 0)
return 1;
}
}
return 0;
}
int cauta_binar() {
int st = 0, dr = INF, last = 0;
while (st <= dr) {
int mid = (st + dr) / 2;
if (solve(mid)) {
last = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
return last;
}
int main() {
fin >> N >> M >> R >> C;
rep(i, 1, N)
rep(j, 1, M) {
fin >> a[i][j]; a[i][j] *= 1000;
a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j];
}
rep(i, 1, 2 * N)
rep(j, 1, 2 * N)
sumR[i][j] = sumR[i - 1][j] + a[i][j];
fout << fixed << setprecision(3) << (double)cauta_binar() / 1000.0;
return 0;
}