Cod sursa(job #1205138)

Utilizator andreiiiiPopa Andrei andreiiii Data 5 iulie 2014 14:06:06
Problema Balans Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 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)
{
    const int N1 = N, M1 = M, N2 = 2 * N, M2 = 2 * M, RR = R, CC = C;
    vector<double> 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);

    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("%d.%d\n", Sol / 1000, Sol % 1000);
}