Cod sursa(job #3213263)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 12 martie 2024 20:10:02
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
int l,u,n,i;
long long v[30001],st,dr,mij,s[30001],t[30001];
double sol;
deque <int> d;
bool f (long long val)
{
    ///s[i]/t[i]>=y => s[i]>=y*t[i] => s[i]-y*t[i]>=0
    ///s1-y*t1>=0
    ///s2-y*t2>=0
    ///(s1+s2)/(t1+t2)>=y => s1+s2-y*t1-y*t2>=0
    for (int i=1; i<=n; i++)
    {
        v[i]=s[i]-val*t[i];
        v[i]+=v[i-1];
    }
    d.clear ();
    for (int i=l; i<=n; i++)
    {
        while (!d.empty ()&&v[d.back ()]>=v[i-l])
            d.pop_back ();
        d.push_back (i-l);
        if (i>=l)
        {
            if (v[i]-v[d.front ()]>=0)
                return 1;
            if (i-d.front ()==u)
                d.pop_front ();
        }
    }
    return 0;
}
int main()
{
    fin>>n>>l>>u;
    for (i=1; i<=n; i++)
    {
        fin>>s[i];
        s[i]*=1000;
    }
    for (i=1; i<=n; i++)
        fin>>t[i];
    st=0;
    dr=3e10;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (f (mij))
            st=mij+1;
        else
            dr=mij-1;
    }
    sol=(double) dr/1000;
    fout<<fixed<<setprecision (2)<<sol;
    return 0;
}