Pagini recente » Cod sursa (job #845396) | Cod sursa (job #2352261) | Cod sursa (job #726480) | Cod sursa (job #2083598) | Cod sursa (job #1575405)
#include <cstdio>
#include <deque>
using namespace std;
typedef long long ll;
int n, m, r, c, a[302][302];
ll ans = 0;
bool ok(ll x) {
ll b[302][302];
for (int i = 1; i <= 2*n; i++) {
b[i-1][0] = 0;
for (int k = 1; k <= 2*m; k++) {
b[i-1][k] = 0;
}
for (int j = i; j < min(i + r - 1, 2*n); j++) {
b[j][0] = 0;
for (int k = 1; k <= 2*m; k++) {
b[j][k] = b[j][k-1] + b[j-1][k] - b[j-1][k-1] + 1LL * a[j][k] - x;
}
}
for (int j = i + r - 1; j <= min(2*n, i + n - 1); j++) {
b[j][0] = 0;
for (int k = 1; k <= 2*m; k++) {
b[j][k] = b[j][k-1] + b[j-1][k] - b[j-1][k-1] + 1LL * a[j][k] - x;
}
deque<int> d;
for (int k = c; k <= 2*m; k++) {
while (!d.empty() && b[j][k - c] <= b[j][d.front()]) {
d.pop_front();
}
while (!d.empty() && k - d.back() > m) {
d.pop_back();
}
d.push_front(k - c);
if (b[j][k] >= b[j][d.back()]) {
return true;
}
}
}
}
return false;
}
void solve(ll l, ll r) {
ll mid;
while (l <= r) {
mid = l + (r - l) / 2;
if (ok(mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
}
int main() {
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &r, &c);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
a[i][j] *= 1000;
}
}
for (int i = 1; i <= 2*n; i++) {
for (int j = 1; j <= 2*m; j++) {
if (i <= n && j <= n) continue;
int i1 = (i - 1) % n + 1;
int j1 = (j - 1) % m + 1;
a[i][j] = a[i1][j1];
}
}
solve(0, 1LL<<32);
printf("%lld.%03lld\n", ans / 1000, ans % 1000);
return 0;
}