Cod sursa(job #3310540)

Utilizator petric_mariaPetric Maria petric_maria Data 15 septembrie 2025 00:17:04
Problema Secventa 3 Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");

int n, l, u, s[30005], t[30005], x;
double ans = 0.0;
deque <int> d, poz;

int main()
{
    f >> n >>l >> u;
    s[0] = 0;   t[0] = 0;

    for (int i=1; i<=n; ++i) {
        f >> x;
        s[i] = s[i-1] + x;
    }
    for (int i=1; i<=n; ++i) {
        f >> x;
        t[i] = t[i-1] + x;
    }

    for (int i=1; i<=n; ++i) {
        int aux = 0;
        if (i >= u)
            aux = i-u;

        while (!d.empty() &&
               1.0 * (s[i] - s[aux]) / (t[i] - t[aux]) > 1.0 * (d.back() - s[aux]) / (t[poz.back()] - t[aux]) ) {
            d.pop_back();  poz.pop_back();
        }

        d.push_back (s[i]);  poz.push_back (i);

        while (poz.front() < i - (u-l)) {
            d.pop_front();  poz.pop_front();
        }

        if (i >= u)
            ans = max (ans, 1.0 * (d.front() - s[i-u]) / (t[poz.front()] - t[i-u]));
    }

    for (int i=n-u+1; i<=n-l+1; ++i) {
        while (poz.front () < i) {
            d.pop_front();  poz.pop_front();
        }
        ans = max (ans, 1.0 * (d.front() - s[i-1]) / (t[poz.front()] - t[i-1]));
    }

    g << fixed << setprecision(2) << ans;
    return 0;
}