Cod sursa(job #1672735)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 3 aprilie 2016 00:47:56
Problema Balans Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

typedef long long ll;

const int Mn = 400;

int n, m, r, c;
ll ans;
ll ar[Mn][Mn], sm[Mn][Mn], row[Mn];

bool ok(ll x)
{
    for (int i = 0; i <= n / 2; i++)
        for (int j = i + r; j - i <= n / 2; j++)
        {
            for (int it = 1; it <= m; it++)
                row[it] = row[it - 1] + sm[j][it] - sm[i][it] - 1LL * x * (j - i);

            deque< ll > dq;
            for (int it = c; it <= m; it++)
            {
                while (!dq.empty() && row[dq.back()] >= row[it - c])
                      dq.pop_back();

                dq.push_back(it - c);
                while (!dq.empty() && it - dq.front() > m / 2)
                   dq.pop_front();

                if (row[it] - row[dq.front()] >= 0)
                   return 1;
            }
        }

    return 0;
}

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("%lld", &ar[i][j]), ar[i + n][j] = ar[i][j + m] = ar[i + n][j + m] = ar[i][j];

    n *= 2;
    m *= 2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ar[i][j] *= 1000, sm[i][j] = sm[i - 1][j] + ar[i][j];

    for (int it = (1 << 25); it; it /= 2)
        if (ok(ans + it))
           ans += it;

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

    return 0;
}