Cod sursa(job #3191147)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 8 ianuarie 2024 21:40:01
Problema Balans Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;

const long long max_size = 321, INF = 1e9 + 1;
const double eps = 1e-6;

double a[max_size][max_size], v[max_size][max_size], sum[max_size];
int n, m, r, c;

bool check (double x)
{
    for (int i = 1; i <= 2 * n; i++)
    {
        for (int j = 1; j <= 2 * m; j++)
        {
            v[i][j] = v[i - 1][j] + a[i][j] - x;
        }
    }
    for (int is = 1; is <= 2 * n; is++)
    {
        for (int ij = is + r - 1; ij <= min(2 * n, is + n - 1); ij++)
        {
            deque <int> dq;
            for (int j = 1; j <= 2 * m; j++)
            {
                sum[j] = sum[j - 1] + v[ij][j] - v[is - 1][j];
                if (j >= c)
                {
                    while (!dq.empty() && dq.front() <= j - m)
                    {
                        dq.pop_front();
                    }
                    while (!dq.empty() && sum[j - c] <= sum[dq.back()])
                    {
                        dq.pop_back();
                    }
                    dq.push_back(j - c);
                    if (sum[j] - sum[dq.front()] >= eps)
                    {
                        return true;
                    }
                }
            }
        }
    }
    return 0;
}

void solve ()
{
    cin >> n >> m >> r >> c;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> 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];
        }
    }
    double ans = 0, st = 0, dr = INF;
    while (abs(st - dr) > eps)
    {
        double m = (st + dr) / 2;
        if (check(m))
        {
            ans = m;
            st = m + eps;
        }
        else
        {
            dr = m - eps;
        }
   //     cout << m << " ";
    }
    cout << fixed << setprecision(3) << ans;
    cout << '\n';
}

signed main ()
{
    #ifdef LOCAL
      freopen("test.in", "r", stdin);
      freopen("test.out", "w", stdout);
    #else
      freopen("balans.in", "r", stdin);
      freopen("balans.out", "w", stdout);
    #endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long t;
    //cin >> t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}