Pagini recente » Cod sursa (job #1459734) | Cod sursa (job #367193) | Cod sursa (job #1541460) | Cod sursa (job #557982) | Cod sursa (job #318257)
Cod sursa(job #318257)
#include <cstdio>
#include <cstring>
#define maxn 311
using namespace std;
long long c[maxn], t[maxn];
int n, m, i, j, l, u, ro, co;
double p[maxn], sum[maxn], rez;
long long deq[maxn], sus, jos;
long long v[maxn][maxn], col[maxn][maxn];
inline bool posibil(double d, int n) {
int i, j;
for (i = 1; i <= n; i++)
p[i] = c[i] - (t[i] * d);
for (i = 1; i <= n; i++)
sum[i] = sum[i - 1] + p[i];
sus = 0; jos = 1;
memset(deq, 0, sizeof(deq));
for (i = 1; i <= n; i++) {
if (i - l > 0) {
while (sum[i - l] < sum[deq[sus]] && sus >= jos)
sus--;
sus++;
deq[sus] = i - l;
}
while (deq[jos] < i - u && jos <= sus)
jos++;
if (sum[i] - sum[deq[jos]] >= 0 && deq[jos] != 0)
return true;
}
return false;
}
bool se_poate(double d) {
int l1, l2, i;
bool ok = 0;
for (l1 = 1; l1 <= n; l1++)
for (l2 = l1 + ro - 1; l2 <= n; l2++)
if (l2 - l1 <= n) {
for (i = 1; i <= m; i++) {
c[i] = col[l2][i] - col[l1 - 1][i];
t[i] = l2 - l1 + 1;
}
if (posibil(d, m))
return true;
}
else
break;
return false;
}
void bsearch(double left, double right) {
double m;
while (left + 0.0001 <= right) {
m = (left + right) / 2;
if (se_poate(m)) {
if (m > rez)
rez = m;
left = m + 0.001;
}
else
right = m - 0.001;
}
}
int main() {
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
scanf("%d%d%d%d", &n, &m, &ro, &co);
l = co; u = m;
// fprintf(stderr, "%d\n", m);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
scanf("%lld", &v[i][j]);
v[i + n][j] = v[i][j + m] = v[i + n][j + m] = v[i][j];
}
n = 2 * n; m = 2 * m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
col[i][j] = col[i - 1][j] + v[i][j];
bsearch(0, 2000000000);
printf("%.3lf\n", rez);
return 0;
}