Cod sursa(job #1575424)

Utilizator algebristulFilip Berila algebristul Data 21 ianuarie 2016 14:49:31
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <cstdio>
#include <deque>

using namespace std;

typedef long long ll;

int n, m, r, c, a[302][302];
ll pre[302], tmp;
ll ans = 0;

bool ok(ll x) {
    deque<int> d;

    for (int i = 1; i <= n; i++) {
        for (int k = 0; k <= 2*m; k++) {
            pre[k] = 0;
        }

        for (int j = i; j < min(i + r - 1, 2*n); j++) {
            tmp = 0;
            for (int k = 1; k <= 2*m; k++) {
                tmp += 1LL * a[j][k] - x;
                pre[k] += tmp;
            }
        }

        for (int j = i + r - 1; j <= min(2*n, i + n - 1); j++) {
            tmp = 0;
            for (int k = 1; k <= 2*m; k++) {
                tmp += 1LL * a[j][k] - x;
                pre[k] += tmp;
            }

            d.clear();
            for (int k = c; k <= 2*m; k++) {
                while (!d.empty() && pre[k - c] <= pre[d.front()])  {
                    d.pop_front();
                }
                while (!d.empty() && k - d.back() > m) {
                    d.pop_back();
                }

                d.push_front(k - c);

                if (pre[k] >= pre[d.back()]) {
                    return true;
                }
            }
        }
    }

    return false;
}

void solve(ll l, ll r) {
    ll mid;

    while (l <= r) {
        mid = l + (r - l) / 2;

        if (ok(mid)) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
}

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

    scanf("%d %d %d %d", &n, &m, &r, &c);

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

    for (int i = 1; i <= 2*n; i++) {
        for (int j = 1; j <= 2*m; j++) {
            if (i <= n && j <= n) continue;
            int i1 = (i - 1) % n + 1;
            int j1 = (j - 1) % m + 1;
            a[i][j] = a[i1][j1];
        }
    }

    solve(0, 1LL<<32);

    printf("%lld.%03lld\n", ans / 1000, ans % 1000);

    return 0;
}