Cod sursa(job #2890632)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 16 aprilie 2022 08:58:43
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");

long long n, l, u, a[200005], b[200005], sum1[200005], sum2[200005];

double ans;

long long verif(long long st1, long long dr1, long long st2, long long dr2)
{
    long long val1 = sum1[dr1] - sum1[st1 - 1];
    long long val2 = sum1[dr2] - sum1[st2 - 1];
    long long timp1 = sum2[dr1] - sum2[st1 - 1];
    long long timp2 = sum2[dr2] - sum2[st2 - 1];

    if (val1 * timp2 >= val2 * timp1)
        return 1;

    return 0;
}

int main()
{
    fin >> n >> l >> u;
    for (long long i = 1; i <= n; i++){
        fin >> a[i];
        sum1[i] = sum1[i - 1] + a[i];
    }

    for (long long i = 1; i <= n; i++) {
        cin >> b[i];
        sum2[i] = sum2[i - 1] + b[i];
    }

    deque<long long>dq;
    for (long long i = 1; i <= n; i++) {
        while (dq.size() && dq.front() < i - u + 1)
            dq.pop_front();
        if (i >= l) {
            while (dq.size() && verif(i - l + 1, i, dq.back(), i))
                dq.pop_back();
            dq.push_back(i - l + 1);
            ans = max(ans, (double)(sum1[i] - sum1[dq.front() - 1]) / (sum2[i] - sum2[dq.front() - 1]));
        }
    }

    fout << fixed << setprecision(3) << ans;
    return 0;
}