Cod sursa(job #1688158)

Utilizator sucureiSucureiRobert sucurei Data 13 aprilie 2016 12:06:20
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <cstring>
#define maxn 311

using namespace std;

long long c[maxn];
int n, m, i, j, l, u, ro, co;
long long sum[maxn], rez;
int deq[maxn], sus, jos;
int v[maxn][maxn];
long long col[maxn][maxn];


inline bool posibil(long long d, int n) {
    int i;

    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + (c[i] - d);

    sus = 0; jos = 1;
    deq[sus] = deq[jos] = 0;
    for (i = l; i <= n; i++) {
        while (sum[i - l] < sum[deq[sus]] && sus >= jos)
            sus--;
        sus++;
        deq[sus] = i - l;

        while (deq[jos] < i - u && jos <= sus)
            jos++;

        if (sum[i] - sum[deq[jos]] >= 0)
            return true;
    }

    return false;
}

inline int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}

inline bool se_poate(int d) {
    int l1, l2, i, n2 = n / 2;

    for (l1 = 1; l1 <= n2; l1++) {
        for (l2 = l1 + ro - 1; l2 <= l1 + n2 - 1; l2++) {
            for (i = 1; i <= m; i++)
                c[i] = col[l2][i] - col[l1 - 1][i];

            if (posibil(1LL * (l2 - l1 + 1) * d, m))
                return true;
        }
    }

    return false;
}

void bsearch(int left, int right) {
    int m;
    while (left <= right) {
        m = (left + right) >> 1;
        if (se_poate(m)) {
            if (m > rez)
                rez = m;
            left = m + 1;
        }
        else
            right = m - 1;
    }
}

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

    scanf("%d%d%d%d", &n, &m, &ro, &co);
    l = co; u = m;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            scanf("%lld", &col[i][j]);
            col[i][j] *= 1000;
            col[i + n][j] = col[i][j + m] = col[i + n][j + m] = col[i][j];
        }

    n = 2 * n; m = 2 * m;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            col[i][j] += col[i - 1][j];

    bsearch(0, 100000000);

    printf("%lld.", rez / 1000);
    if (rez % 1000 == 0) {
        printf("000\n");
        return 0;
    }

    int aux = rez % 1000;
    while (aux * 10 < 1000) {
       printf("0");
       aux *= 10;
    }
    printf("%lld\n", rez % 1000);

    return 0;
}