Pagini recente » Cod sursa (job #1377224) | Cod sursa (job #2277800) | Cod sursa (job #2037690) | Cod sursa (job #2648874) | Cod sursa (job #800702)
Cod sursa(job #800702)
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 320;
int n, m, p, q, x[N][N], bmax;
long long s[N][N], v[N];
long long smax(long long a, long long b) {
return (a > b ? a : b);
}
bool ver() {
int i, d[N];
long long smax = -10000;
d[0] = 0;
for(i = 1; i<=m; ++i)
d[i] = max(v[i] - v[i - 1], d[i - 1] + v[i] - v[i - 1]);
for(i = q; i<=m; ++i)
smax = max(max(smax, v[i] - v[i - q]), d[i - q] + v[i] - v[i - q]);
return smax >= 0;
}
void calc(int l1, int l2) {
int j, i, pas = 1<<30;
for(i = 0; pas; pas>>=1) {
for(j = 1; j<=m; ++j)
v[j] = (s[l2][j] - s[l1 - 1][j])/(l2 - l1 + 1) - i - pas + v[j - 1];
if(ver())
i += pas;
}
bmax = max(bmax, i);
}
int main() {
int i, j;
freopen("balans.in", "r", stdin);
freopen("balans.out", "w", stdout);
cin >> n >> m >> p >> q;
for(i = 1; i<=n; ++i)
for(j = 1; j<=m; ++j)
cin >> x[i][j], x[i][j] *= 1000;
for(i = 1; i<=n; ++i)
for(j = 1; j<=m; ++j)
x[i][j + m] = x[i][j];
m*=2;
for(i = 1; i<=n; ++i)
for(j = 1; j<=m; ++j)
x[i + n][j] = x[i][j];
n*=2;
for(j = 1; j<=m; ++j)
for(i = 1; i<=n; ++i)
s[i][j] = s[i - 1][j] + x[i][j];
for(i = 1; i<=n - p + 1; ++i)
for(j = i + p - 1; j<=n; ++j)
calc(i, j);
cout << (double)bmax/1000;
return 0;
}