Cod sursa(job #804280)

Utilizator deneoAdrian Craciun deneo Data 29 octombrie 2012 15:55:18
Problema Balans Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#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;
}