Cod sursa(job #946954)

Utilizator deneoAdrian Craciun deneo Data 6 mai 2013 13:42:34
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <deque>
using namespace std;

ifstream fin("balans.in");
ofstream fout("balans.out");

#define rep(i, st, fn) for(int (i) = (st); (i) <= (fn); ++(i))
#define ll long long

const int MAXN = 310;
const int INF = 100000 * 1000;

int N, M, R, C;
int a[MAXN][MAXN],
ll sumR[MAXN][MAXN], sumC[MAXN];

deque<int> dq;

void insert_deque(int elem) {
    while (!dq.empty() && sumC[dq.back()] > sumC[elem])
        dq.pop_back();
    dq.push_back(elem);
}

int get_deque(int limit) {
    while (!dq.empty() && dq.front() < limit)
        dq.pop_front();
    return dq.front();
}

bool solve(int mid) {
    for (int i = 1; i <= 2 * N; ++i)
        for (int j = i + R - 1; j - i < N && j <= 2 * N; ++j) {
            dq.clear();
            rep(k, 1, 2 * M)
                sumC[k] = sumC[k - 1] + (sumR[j][k] - sumR[i - 1][k] - 1LL * mid * (j - i + 1));
            rep(k, C, 2 * M) {
                insert_deque(k - C);
                if (sumC[k] - sumC[get_deque(k - M)] >= 0)
                    return 1;
            }
        }
    return 0;
}

int cauta_binar() {
    int st = 0, dr = INF, last = 0;

    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (solve(mid)) {
            last = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }

    return last;
}

int main() {
    fin >> N >> M >> R >> C;

    rep(i, 1, N)
        rep(j, 1, M) {
            fin >> a[i][j]; a[i][j] *= 1000;
            a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j];
        }

    rep(i, 1, 2 * N)
        rep(j, 1, 2 * N)
            sumR[i][j] = sumR[i - 1][j] + a[i][j];

    fout << fixed << setprecision(3) << (double)cauta_binar() / 1000.0;
    return 0;
}