Pagini recente » Cod sursa (job #359156) | Cod sursa (job #1921729) | Cod sursa (job #2332772)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
const int NMAX = 305;
int n, m, r, c;
ll ans;
ll v[NMAX];
ll val[NMAX];
ll a[NMAX][NMAX];
ll sum_col[NMAX][NMAX];
template <class T>
void maxi (T &a, T b) {
a = max (a, b);
}
bool check (ll x) {
for (int i = 1; i <= 2 * m; ++i) {
v[i] = val[i] - x;
v[i] += v[i - 1];
}
deque <ll> dq;
for (int i = c; i <= 2 * m; ++i) {
while (!dq.empty() && i - dq.front() > m) {
dq.pop_front();
}
if (i >= c) {
while (!dq.empty() && v[dq.back()] >= v[i - c]) {
dq.pop_back();
}
dq.pb (i - c);
if (v[i] - v[dq.front()] >= 0) {
return true;
}
}
}
return false;
}
ll binSearch (int dist) {
if (!check (ans * dist)) return ans;
ll lo = ans, hi = 1e8;
while (lo != hi) {
ll mid = lo + (hi - lo + 1) / 2;
if (check (mid * dist)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif
freopen ("balans.in", "r", stdin);
freopen ("balans.out", "w", stdout);
scanf ("%d%d%d%d\n", &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;
a[i + n][j] = a[i][j + m] = a[i + n][j + m] = a[i][j];
}
}
for (int i = 1; i <= 2 * n; ++i) {
for (int j = 1; j <= 2 * m; ++j) {
sum_col[i][j] = sum_col[i - 1][j] + a[i][j];
}
}
ans = 0;
for (int l1 = 1; l1 <= 2 * n - r + 1; ++l1) {
int lim = min (l1 + n - 1, 2 * n);
for (int l2 = l1 + r - 1; l2 <= lim; ++l2) {
for (int i = 1; i <= 2 * m; ++i) {
val[i] = sum_col[l2][i] - sum_col[l1 - 1][i];
}
maxi (ans, binSearch (l2 - l1 + 1));
}
}
printf ("%.3f\n", ans / 1000.0);
fclose (stdin);
fclose (stdout);
#ifdef LOCAL_DEFINE
fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
return 0;
}