Cod sursa(job #3222935)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 11 aprilie 2024 21:59:20
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
const int N=200'000;
int n,l,r;
double timp[N+1],sum[N+1];
double calc(int poz,double x)
{
    return -x*timp[poz]+sum[poz];
}
bool is_good(double x)
{
    deque<int>d;
    for(int i=l;i<=n;i++)
    {
        if(d.size() && d.front() == i-r-1)
        {
            d.pop_front();
        }
        while(d.size() && calc(d.back(),x) >= calc(i-l,x))
        {
            d.pop_back();
        }
        d.push_back(i-l);
        if(calc(i,x)>=calc(d.front(),x))
        {
            return true;
        }
    }
    return false;
}
int main()
{
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        timp[i]=timp[i-1]+x;
    }
    double l=0,r=sum[n];
    while(r-l>=0.001)
    {
        double m=(l+r)/2;
        if(is_good(m))
        {
            l=m;
        }
        else
        {
            r=m;
        }
    }
    cout<<fixed<<setprecision(3)<<l;
    return 0;
}