Cod sursa(job #2907874)

Utilizator AswVwsACamburu Luca AswVwsA Data 31 mai 2022 19:15:34
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <cstdio>
#include <deque>
#include <cmath>
#include <iomanip>
#define ll long long
using namespace std;

int d[30003], t[30003], l, u, n;
int s[30003];

int main()
{
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");
    int i;
    cin >> n >> l >> u;
    for (i = 1; i <= n; i++)
    {
        cin >> d[i];
        s[i] = s[i - 1] + d[i];
    }
    for (i = 1; i <= n; i++)
        cin >> t[i];
    /*double med, st = 0.0, dr = s[n], sol;
    for (int nr = 1; nr <= 100; nr++)
    {
        med = (st + dr) / 2;
        if (ok(med))
        {
            sol = med;
            st = med + 1;
        }
        else
            dr = med - 1;
    }
    cout << fixed << setprecision(2) << sol;*/
    deque <int> dq;
    int dist, timp;
    dist = timp = 0;
    double mx = 0;
    for (i = 1; i <= n; i++)
    {
        while (!dq.empty() and dq.front() <= i - u)
        {
            dist -= d[dq.front()];
            timp -= t[dq.front()];
            dq.pop_front();
        }
        //(dist - d[dq.back()] + d[i]) / (timp - t[dq.back()] + t[i]) > dist / timp
        //<=> (dist - d[dq.back()] + d[i]) * timp > (timp - t[dq.back()] + t[i]) * dist
        while (!dq.empty() and (dist - d[dq.back()] + d[i]) * timp > (timp - t[dq.back()] + t[i]) * dist)
        {
            dist -= d[dq.back()];
            timp -= t[dq.back()];
            dq.pop_back();
        }
        dq.push_back(i);
        dist += d[i];
        timp += t[i];
        mx = max(mx, 1.0 * dist / timp);
    }
    cout << fixed << setprecision(2) << mx;
}