Cod sursa(job #1205131)

Utilizator andreiiiiPopa Andrei andreiiii Data 5 iulie 2014 13:48:09
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 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], SumC[2 * Nmax][2 * Nmax];
double SumL[2 * Nmax];
int N, M, R, C;

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

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

                if (SumL[i] - SumL[D.front()] >= -EPS) 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]);

    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) / 1000.0))
            Sol |= step;
    }

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