Cod sursa(job #1497334)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 6 octombrie 2015 17:52:12
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <iomanip>
#include <deque>

using namespace std;

const int NMAX = 155;

int n, m, r, c;
int mat[2 * NMAX][2 * NMAX];

double s_part[2 * NMAX];
deque <int> coada;

bool exists (double x) {
    int j, k;
    double sum;

    for (int i = 1; i <= 2 * n; ++ i) {
        for (k = 1; k <= 2 * m; ++ k)
            s_part[k] = 0;

        for (j = i; j <= 2 * n && j <= i + n - 1; ++ j) {
            sum = 0;
            for (k = 1; k <= 2 * m; ++ k) {
                sum += (mat[j][k] - x);
                s_part[k] += sum;
            }

            if (j < i + r - 1)
                continue ;

            coada.clear();

            for (k = 1; k <= 2 * m; ++ k) {
                while (!coada.empty() && coada.front() <= k - n)
                    coada.pop_front();

                if (i >= c) {
                    while (!coada.empty() && s_part[coada.back()] <= s_part[i - c])
                        coada.pop_back();
                    coada.push_back(i - c);


                    if (s_part[i] - s_part[coada.front()] >= 0)
                        return true;
                }
            }
        }
    }

    return false;
}

int main()
{
    //ifstream cin("balans.in");
    //ofstream cout("balans.out");

    cin >> n >> m >> r >> c;

    int j;
    for (int i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            cin >> mat[i][j];

    for (int i = 1; i <= 2 * n; ++ i)
        for (j = 1; j <= 2 * m; ++ j)
            mat[i][j] = mat[(i - 1) % n + 1][(j - 1) % m + 1];

    double st = -100000;
    double dr = 100000;
    double mijl;

    for (int steps = 0; steps < 35; ++ steps) {
        mijl = (st + dr) * 0.5;

        if (exists(mijl))
            st = mijl;
        else
            dr = mijl;
    }

    cout << fixed << setprecision(3) << st << '\n';

    //cin.close();
    //cout.close();
    return 0;
}