Cod sursa(job #1232044)

Utilizator smaraldaSmaranda Dinu smaralda Data 21 septembrie 2014 22:16:56
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<deque>
using namespace std;

const int NMAX = 305;

int n, m, lo, hi, r, c, n2, m2, a[NMAX][NMAX], sumMat[NMAX][NMAX], sumCol[NMAX][NMAX];
deque <int> q;

inline int sum (int col) {
    return sumCol[lo][col] - sumCol[hi - 1][col];
}

inline void insert (int col) {
    while(!q.empty() && sum(col) <= sum(q.back()))
        q.pop_back();
    q.push_back(col);
}

inline int matrix (int left, int right) {
    return sumMat[lo][right] - sumMat[hi - 1][right] - sumMat[lo][left - 1] + sumMat[hi - 1][left - 1];
}

bool ok (int mid) {
    int i, j;

    for(i = 1; i <= n2; ++ i)
        for(j = 1; j <= m2; ++ j) {
            sumCol[i][j] = sumCol[i - 1][j] + a[i][j] - mid;
            sumMat[i][j] = sumMat[i][j - 1] + sumCol[i][j];
        }

    for(hi = 1; hi <= n2; ++ hi)
        for(lo = hi + r - 1; lo < hi + n && lo <= n2; ++ lo) {
            q.clear();

            for(j = c; j <= m2; ++ j) {
                insert(j - c);
                while(q.front() < j - m)
                    q.pop_front();

                if(matrix(q.back(), j) >= 0)
                    return 1;
            }
        }
    return 0;
}

int bs (int left, int right) {
    int last, mid;

    while(left <= right) {
        mid = (left + right) / 2;
        fprintf(stderr, "%d\n", mid);
        if(ok(mid)) {
            last = mid;
            left = mid + 1;
        }
        else 
            right = mid - 1;
    }
    return last;
}

int main() {
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);
    int i, j, valmax;

    scanf("%d%d%d%d", &n, &m, &r, &c);
    n2 = 2 * n;
    m2 = 2 * m;
    valmax = -1;
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= m; ++ j) {
            scanf("%d", &a[i][j]);
            a[i][j] *= 1000;

            valmax = max(valmax, a[i][j]);
            a[i + n][j] = a[i][j + m] = a[i][j];            
        }

    printf("%.3lf", (double)bs(0, valmax) / 1000);
    return 0;
}