Pagini recente » Cod sursa (job #2178179) | Cod sursa (job #2817394) | Cod sursa (job #294510) | Cod sursa (job #3247298) | Cod sursa (job #3191155)
#include <bits/stdc++.h>
using namespace std;
const long long max_size = 321, INF = 1e8 + 1;
const double eps = 1e-4;
long long a[max_size][max_size], v[max_size][max_size], sum[max_size];
long long n, m, r, c;
bool check (long long x)
{
for (long long i = 1; i <= 2 * n; i++)
{
for (long long j = 1; j <= 2 * m; j++)
{
v[i][j] = v[i - 1][j] + a[i][j] - x;
}
}
for (long long is = 1; is <= n; is++)
{
for (long long ij = is + r - 1; ij <= min(2 * n, is + n - 1); ij++)
{
deque <long long> dq;
for (long long j = 1; j <= 2 * m; j++)
{
sum[j] = sum[j - 1] + v[ij][j] - v[is - 1][j];
if (j >= c)
{
while (!dq.empty() && dq.front() <= j - m)
{
dq.pop_front();
}
while (!dq.empty() && sum[j - c] <= sum[dq.back()])
{
dq.pop_back();
}
dq.push_back(j - c);
if (sum[j] - sum[dq.front()] >= 0)
{
return true;
}
}
}
}
}
return 0;
}
void solve ()
{
cin >> n >> m >> r >> c;
for (long long i = 1; i <= n; i++)
{
for (long long j = 1; j <= m; j++)
{
cin >> a[i][j];
a[i][j] *= 1000;
a[i + n][j] = a[i][j];
a[i][j + m] = a[i][j];
a[i + n][j + m] = a[i][j];
}
}
long long ans = 0, st = 0, dr = INF;
while (st <= dr)
{
long long m = (st + dr) / 2;
if (check(m))
{
ans = m;
st = m + 1;
}
else
{
dr = m - 1;
}
// cout << m << " ";
}
cout << fixed << setprecision(3) << (float) ans / 1000;
cout << '\n';
}
signed main ()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long t;
//cin >> t;
t = 1;
while (t--)
{
solve();
}
return 0;
}