Pagini recente » Cod sursa (job #2724460) | Cod sursa (job #227377) | Cod sursa (job #2086967) | Cod sursa (job #131699) | Cod sursa (job #963125)
Cod sursa(job #963125)
#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 = 301;
const int INF = 100001 * 1000;
int N, M, R, C;
int a[MAXN][MAXN];
ll sumR[MAXN][MAXN];
bool solve(int mid) {
ll sumC[MAXN];
int dq[MAXN], front = 1, back = 0;
for (int i = 1; i <= 2 * N; ++i)
for (int j = i + R - 1; j - i < N && j <= 2 * N; ++j) {
front = 1; back = 0;
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) {
while (front <= back && sumC[dq[back]] > sumC[k - C])
--back;
dq[++back] = k - C;
while (front <= back && dq[front] < k - M)
++front;
int rez = dq[front];
if (sumC[k] - sumC[rez] >= 0)
return 1;
}
}
return 0;
}
int cauta_binar() {
int st = 0, dr = INF, last = 0;
while (st <= dr) {
int mid = (st + dr) >>1;
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;
}