Cod sursa(job #1398118)

Utilizator Ionut228Ionut Calofir Ionut228 Data 23 martie 2015 23:57:19
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <deque>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream fin("balans.in");
ofstream fout("balans.out");

const double eps = 1e-3;

int N, M, R, C;
double sol;
int A[305][305];
double sum[305][305], sumC[305];
deque<int> DQ;

bool solve(double cost)
{
    for (int i = 1; i <= 2 * N; ++i)
        for (int j = i + R - 1; j - i + 1 <= N && j <= 2 * N; ++j)
        {
            for (int k = 1; k <= 2 * M; ++k)
                sumC[k] = sumC[k - 1] + sum[j][k] - sum[i - 1][k] - cost * (j - i + 1);

            DQ.clear();

            for (int k = C; k <= 2 * M; ++k)
            {
                while (!DQ.empty() && sumC[k - C + 1] <= sumC[DQ.back() - 1])
                    DQ.pop_back();
                DQ.push_back(k - C + 1);

                while (DQ.front() < k - M + 1)
                    DQ.pop_front();

                if (sumC[k] - sumC[DQ.front() - 1] >= eps)
                    return true;
            }
        }

    return false;
}

void cb()
{
    double lt = 0.0, rt = 100001.0;
    while (rt - lt > eps)
    {
        double mid = (lt + rt) / 2.0;

        if (solve(mid))
        {
            sol = mid;
            lt = mid;
        }
        else
            rt = mid;
    }
}

int main()
{
    fin >> N >> M >> R >> C;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            fin >> A[i][j];

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

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

    cb();

    fout << fixed << setprecision(3) << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}