Cod sursa(job #1205149)

Utilizator andreiiiiPopa Andrei andreiiii Data 5 iulie 2014 14:42:20
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <algorithm>
#include <cstdio>
#include <deque>

using namespace std;

const int Nmax = 155;
const double EPS = 1e-8;

int Values[2 * Nmax][2 * Nmax];
long long SumC[2 * Nmax][2 * Nmax], SumL[2 * Nmax];
int N, M, R, C;

bool Check(const int t)
{
    for (int up = 0; up <= N; up++)
    {
        for (int down = up + R; down - up <= N; down++)
        {
            for (int i = 1; i <= 2 * M; i++)
                SumL[i] = SumL[i - 1] + SumC[down][i] - SumC[up][i] - 1LL * t * (down - up);

            deque<int> D;
            for (int i = C; i <= 2 * M; i++)
            {
                while (!D.empty() && SumL[i - C] <= SumL[D.back()]) D.pop_back();
                D.push_back(i - C);

                while (!D.empty() && i - D.front() > M) D.pop_front();

                if (SumL[i] - SumL[D.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", &Values[i][j]);
            Values[i][j] *= 1000;
        }
    }

    for (int i = N + 1; i <= 2 * N; i++)
        for (int j = 1; j <= M; j++)
            Values[i][j] = Values[i - N][j];

    for (int i = 1; i <= 2 * N; i++)
        for (int j = M + 1; j <= 2 * M; j++)
            Values[i][j] = Values[i][j - M];

    for (int i = 1; i <= 2 * N; i++)
        for (int j = 1; j <= 2 * M; j++)
            SumC[i][j] = SumC[i - 1][j] + Values[i][j];

    int Sol = 0;
    for (int step = (1 << 26); step; step >>= 1)
    {
        if (Check(Sol | step))
            Sol |= step;
    }

    printf("%.3lf\n", Sol / 1000.0);
}