Cod sursa(job #1232144)

Utilizator smaraldaSmaranda Dinu smaralda Data 22 septembrie 2014 10:26:38
Problema Balans Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<deque>
using namespace std;

#define LL int

const int NMAX = 310;

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

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

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

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

            for(j = c; j <= m2; ++ j) {
                while(!q.empty() && q.front() < j - c)  q.pop_front();
                while(!q.empty() && sumCol[hi][q.back()] - sumCol[lo - 1][q.back()] >= sumCol[hi][j - c] - sumCol[lo - 1][j - c]) q.pop_back();
                q.push_back(j - c);

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

LL bs (LL left, LL right) {
    LL last, mid;
    while(left <= right) {
        mid = (left + right) / 2; 
        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;
    LL res;

    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\n", (double)bs(0, valmax) / 1000);
    return 0;
}