Cod sursa(job #1575405)

Utilizator algebristulFilip Berila algebristul Data 21 ianuarie 2016 14:39:02
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <deque>

using namespace std;

typedef long long ll;

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

bool ok(ll x) {
    ll b[302][302];

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

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

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

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

                d.push_front(k - c);

                if (b[j][k] >= b[j][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;
}