Pagini recente » Cod sursa (job #2415015) | Cod sursa (job #832362) | Cod sursa (job #973166) | Cod sursa (job #255539) | Cod sursa (job #1232044)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<deque>
using namespace std;
const int NMAX = 305;
int n, m, lo, hi, r, c, n2, m2, a[NMAX][NMAX], sumMat[NMAX][NMAX], sumCol[NMAX][NMAX];
deque <int> q;
inline int sum (int col) {
return sumCol[lo][col] - sumCol[hi - 1][col];
}
inline void insert (int col) {
while(!q.empty() && sum(col) <= sum(q.back()))
q.pop_back();
q.push_back(col);
}
inline int matrix (int left, int right) {
return sumMat[lo][right] - sumMat[hi - 1][right] - sumMat[lo][left - 1] + sumMat[hi - 1][left - 1];
}
bool ok (int mid) {
int i, j;
for(i = 1; i <= n2; ++ i)
for(j = 1; j <= m2; ++ j) {
sumCol[i][j] = sumCol[i - 1][j] + a[i][j] - mid;
sumMat[i][j] = sumMat[i][j - 1] + sumCol[i][j];
}
for(hi = 1; hi <= n2; ++ hi)
for(lo = hi + r - 1; lo < hi + n && lo <= n2; ++ lo) {
q.clear();
for(j = c; j <= m2; ++ j) {
insert(j - c);
while(q.front() < j - m)
q.pop_front();
if(matrix(q.back(), j) >= 0)
return 1;
}
}
return 0;
}
int bs (int left, int right) {
int last, mid;
while(left <= right) {
mid = (left + right) / 2;
fprintf(stderr, "%d\n", mid);
if(ok(mid)) {
last = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return last;
}
int main() {
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
int i, j, valmax;
scanf("%d%d%d%d", &n, &m, &r, &c);
n2 = 2 * n;
m2 = 2 * m;
valmax = -1;
for(i = 1; i <= n; ++ i)
for(j = 1; j <= m; ++ j) {
scanf("%d", &a[i][j]);
a[i][j] *= 1000;
valmax = max(valmax, a[i][j]);
a[i + n][j] = a[i][j + m] = a[i][j];
}
printf("%.3lf", (double)bs(0, valmax) / 1000);
return 0;
}