Pagini recente » Cod sursa (job #488160) | Cod sursa (job #317031) | Cod sursa (job #1274994) | Cod sursa (job #1938578) | Cod sursa (job #804280)
Cod sursa(job #804280)
#include <fstream>
#include <deque>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream fin("balans.in");
ofstream fout("balans.out");
#define MAXN 160 * 2
#define inf 1 << 16 //mareste
long long n1, n2, r, c, m[MAXN][MAXN], sumpart[MAXN][MAXN];
double sum[MAXN];
deque<int> dq;
double getSum(int col, int st, int fn, double med) {
return (double)(sumpart[col][fn] - sumpart[col][st - 1]) - (double)(fn - st + 1) * med;
}
void push_deque(int p) {
while (!dq.empty() && sum[dq.back()] > sum[p])
dq.pop_back();
dq.push_back(p);
}
double get_deque() {
return sum[dq.front()];
}
void doSumePartiale() {
for (int i = 1; i <= n1; ++i)
for (int j = 1; j <= n2; ++j)
sumpart[j][i] = sumpart[j][i - 1] + m[i][j];
}
double doWildSol(double med) {
int i, j, k;
double maxsum = -inf;
for (i = 1; i <= n1; ++i)
for (j = i + r - 1; j <= n1; ++j) {
memset(sum, 0, sizeof(sum));
dq.clear();
for (k = 1; k <= n2; ++k) {
sum[k] = (double)sum[k - 1] + getSum(k, i, j, med);
if (k >= c) {
push_deque(k - c);
maxsum = max(maxsum, sum[k] - get_deque());
}
}
}
return maxsum;
}
double cautareBinare() {
double i, mid = 0;
for (i = inf; i > 0.0001; i /= 2) {
if (doWildSol(mid + i) >= 0)
mid += i;
}
return mid;
}
int main() {
int i, j;
fin >> n1 >> n2 >> r >> c;
for (i = 1; i <= n1; ++i)
for (j = 1; j <= n2; ++j) {
fin >> m[i][j];
m[i + n1][j] = m[i][j + n2] = m[i + n1][j + n2] = m[i][j];
}
n1 *= 2; n2 *= 2;
doSumePartiale();
freopen("balans.out", "w", stdout);
printf("%.3f", (double)cautareBinare());
return 0;
}