Cod sursa(job #1205144)

Utilizator andreiiiiPopa Andrei andreiiii Data 5 iulie 2014 14:32:25
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <algorithm>
#include <cstdio>
#include <deque>

using namespace std;

const int BufferSize = 8000000;
char Buffer[BufferSize];
int BufferCursor;

void Read(int &N)
{
    N = 0;
    while (Buffer[BufferCursor] >= '0' && Buffer[BufferCursor] <= '9')
    {
        N = 10 * N + Buffer[BufferCursor] - '0';
        BufferCursor++;
        if (BufferCursor == BufferSize)
        {
            BufferCursor = 0;
            fread(Buffer, 1, BufferSize, stdin);
        }
    }

    BufferCursor++;
    if (BufferCursor == BufferSize)
    {
        BufferCursor = 0;
        fread(Buffer, 1, BufferSize, stdin);
    }
}

const int Nmax = 155;

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

bool Check(const long long t)
{
    const int N1 = N, M1 = M, N2 = 2 * N, M2 = 2 * M, RR = R, CC = C;
    vector<long long> SumL(M2 + 1, 0);

    for (int up = 0; up + RR <= N2; up++)
    {
        for (int down = up + RR; down <= N2 && down - up <= N1; down++)
        {
            for (int i = 1; i <= M2; i++)
                SumL[i] = SumL[i - 1] + SumC[down][i] - SumC[up][i] - t * (down - up);

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

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

                if (!D.empty() && SumL[i] - SumL[D.front()] >= 0) return 1;
            }
        }
    }

    return 0;
}

int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);

    fread(Buffer, 1, BufferSize, stdin);
    Read(N); Read(M); Read(R); Read(C);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            Read(Values[i][j]);
            Values[i][j] *= 1000;

            Values[i + N][j] = Values[i][j + M] = Values[i + N][j + M] = Values[i][j];
        }
    }

    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 l = 0, r = 100000000, Sol = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (Check(mid))
        {
            Sol = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }

    printf("%d.%d\n", Sol / 1000, Sol % 1000);
}