Cod sursa(job #2917282)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 4 august 2022 11:13:24
Problema Balans Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
/// Preset de infoarena
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

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

const int maxN = 305;
const double eps = 1e-6;
int n, m, r, c;
int mat[maxN][maxN];
double aux[maxN][maxN], v[maxN];
deque <int> dq;

bool check(double val)
{
    for(int i = 1; i <= 2*n; i++)
        for(int j = 1; j <= 2*m; j++)
            aux[i][j] = aux[i - 1][j] + mat[i][j] - val;
    for(int i1 = 1; i1 <= n; i1++)
    {
        for(int i2 = i1 + r - 1; i2 <= min(2 * n, i1 + n); i2++)
        {
            dq.clear();
            for(int j = 1; j <= 2 * m; j++)
            {
                v[j] = v[j - 1] + (aux[i2][j] - aux[i1 - 1][j]);
                if(j >= c)
                {
                    while(!dq.empty() && v[j - c] <= v[dq.back()])
                        dq.pop_back();
                    dq.push_back(j - c);
                    if(dq.front() == j - m)
                        dq.pop_front();
                    if(v[j] - v[dq.front()] >= 0)
                        return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    fin >> n >> m >> r >> c;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            fin >> mat[i][j];
            mat[i + n][j] = mat[i][j];
            mat[i][j + n] = mat[i][j];
            mat[i + n][j + n] = mat[i][j];
        }
    }
    double st = 0, dr = 100000, ans = 0;
    while(st + eps <= dr)
    {
        double med = (st + dr) / 2;
        if(check(med))
        {
            ans = med;
            st = med;
        }
        else
            dr = med;
    }
    fout << fixed << setprecision(3) << ans;
    return 0;
}