Pagini recente » Cod sursa (job #902181) | Cod sursa (job #892313) | Cod sursa (job #675824) | Cod sursa (job #936162) | Cod sursa (job #1232140)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<deque>
using namespace std;
#define LL long long
const int NMAX = 310;
int n, m, lo, hi, r, c, n2, m2, a[NMAX][NMAX];
LL sumMat[NMAX][NMAX], sumCol[NMAX][NMAX];
deque <int> q;
inline LL matrix (int left, int right) {
return sumMat[hi][right] - sumMat[lo - 1][right] - sumMat[hi][left - 1] + sumMat[lo - 1][left - 1];
}
bool ok (LL mid) {
int i, j;
for(i = 1; i <= n2; ++ i)
for(j = 1; j <= m2; ++ j) {
sumCol[i][j] = sumCol[i - 1][j] + (LL)a[i][j] - mid;
sumMat[i][j] = sumMat[i][j - 1] + sumCol[i][j];
}
for(lo = 1; lo <= n; ++ lo)
for(hi = lo + r - 1; hi <= n2 && hi < lo + n; ++ hi) {
q.clear();
for(j = c; j <= m2; ++ j) {
while(!q.empty() && q.front() < j - c) q.pop_front();
while(!q.empty() && sumCol[hi][q.back()] - sumCol[lo - 1][q.back()] >= sumCol[hi][j - c] - sumCol[lo - 1][j - c]) q.pop_back();
q.push_back(j - c);
if(matrix(q.front() + 1, j) >= 0)
return 1;
}
}
return 0;
}
LL bs (LL left, LL right) {
LL last, mid;
while(left <= right) {
mid = (left + right) / 2;
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;
LL res;
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];
}
res = bs(0, valmax);
printf("%lld.%lld\n", res / 1000, res % 1000);
return 0;
}