Cod sursa(job #953071)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:45:55
Problema Balans Scor 100
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 = 301;
const int INF = 100001 * 1000;
 
int N, M, R, C;
int a[MAXN][MAXN];
ll sumR[MAXN][MAXN];
 
bool solve(int mid) {
    ll sumC[MAXN];
    int dq[MAXN], front = 1, back = 0;
    for (int i = 1; i <= 2 * N; ++i)
        for (int j = i + R - 1; j - i < N && j <= 2 * N; ++j) {
            front = 1; back = 0;
            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) {
                while (front <= back && sumC[dq[back]] > sumC[k - C])
                    --back;
                dq[++back] = k - C;
                while (front <= back && dq[front] < k - M)
                    ++front;
                int rez = dq[front];
                if (sumC[k] - sumC[rez] >= 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;
}