Cod sursa(job #1672871)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 3 aprilie 2016 10:56:58
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 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, mx;
int ans;
int ar[Mn][Mn];
ll sm[Mn][Mn], cl[Mn];

bool ok()
{
    deque< int > dq;
    for (int i = c; i <= m; i++)
    {
        while (!dq.empty() && cl[i - c] <= cl[dq.back()])
              dq.pop_back();

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

        if (cl[i] - cl[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("%d", &ar[i][j]);
            ar[i][j] *= 1000;
            ar[i + n][j] = ar[i][j + m] = ar[i + n][j + m] = ar[i][j];
            mx = max(mx, ar[i][j]);
        }

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

    for (int i = 0; i < n / 2; i++)
        for (int j = i + r; j - i <= n / 2; j++)
        {
            int aux = 0;
            for (int it = 1 << 30; it; it /= 2)
                if (aux + it <= mx && aux + 2 * it - 1 > ans)
                {
                    for (int l = 1; l <= m; l++)
                        cl[l] = cl[l - 1] + (sm[j][l] - sm[i][l]) - 1LL * (j - i) * (aux + it);

                    if (ok())
                       aux += it;
                }

            ans = max(ans, aux);
        }

    printf("%.3f\n", (double)ans / 1000);

    return 0;
}