Pagini recente » Cod sursa (job #92376) | Cod sursa (job #2657776) | Cod sursa (job #2097228) | Cod sursa (job #3129741) | Cod sursa (job #1672871)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
const int Mn = 400;
int n, m, r, c, mx;
int ans;
int ar[Mn][Mn];
ll sm[Mn][Mn], cl[Mn];
bool ok()
{
deque< int > dq;
for (int i = c; i <= m; i++)
{
while (!dq.empty() && cl[i - c] <= cl[dq.back()])
dq.pop_back();
dq.push_back(i - c);
while (!dq.empty() && i - dq.front() > m / 2)
dq.pop_front();
if (cl[i] - cl[dq.front()] >= 0)
return 1;
}
return 0;
}
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", &ar[i][j]);
ar[i][j] *= 1000;
ar[i + n][j] = ar[i][j + m] = ar[i + n][j + m] = ar[i][j];
mx = max(mx, ar[i][j]);
}
n *= 2;
m *= 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sm[i][j] = sm[i - 1][j] + ar[i][j];
for (int i = 0; i < n / 2; i++)
for (int j = i + r; j - i <= n / 2; j++)
{
int aux = 0;
for (int it = 1 << 30; it; it /= 2)
if (aux + it <= mx && aux + 2 * it - 1 > ans)
{
for (int l = 1; l <= m; l++)
cl[l] = cl[l - 1] + (sm[j][l] - sm[i][l]) - 1LL * (j - i) * (aux + it);
if (ok())
aux += it;
}
ans = max(ans, aux);
}
printf("%.3f\n", (double)ans / 1000);
return 0;
}