Cod sursa(job #1398106)

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

using namespace std;

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

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

bool solve(int 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] - 1LL * cost * (j - i + 1);

            while (!DQ.empty())
                DQ.pop_back();

            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] >= 0)
                    return true;
            }
        }

    return false;
}

void cb()
{
    int lt = 0, rt = 100001 * 1000;
    while (rt - lt > 1)
    {
        int mid = (lt + rt) / 2;

        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][j] *= 1000;

            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] + A[i][j];

    cb();

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

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