Cod sursa(job #2917286)

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

using namespace std;

ifstream fin("balans.in");
ofstream fout("balans.out");
#define int long long

const int maxN = 305;
int n, m, r, c;
int mat[maxN][maxN];
int aux[maxN][maxN], v[maxN];

bool check(int 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 - 1); i2++)
        {
            deque <int> dq;
            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;
}

signed 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][j] *= 1000;
            mat[i + n][j] = mat[i][j];
            mat[i][j + n] = mat[i][j];
            mat[i + n][j + n] = mat[i][j];
        }
    }
    int st = 0, dr = 1e8, ans = 0;
    while(st <= dr)
    {
        int med = (st + dr) / 2;
        if(check(med))
        {
            ans = med;
            st = med + 1;
        }
        else
            dr = med - 1;
    }
    double sol = 1.00 * ans / 1000;
    fout << fixed << setprecision(3) << sol;
    return 0;
}