Cod sursa(job #3217785)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 24 martie 2024 17:59:47
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 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,mid,C[30001],T[30001];
double sol;
bool check(long long val)
{
    ///C[i]/T[i]>=y => C[i]-y*T[i]>=0
    for(int i=1;i<=n;i++)
    {
        V[i]=C[i]-val*T[i];
        V[i]+=V[i-1];
    }
    deque <int> d;
    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(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>>C[i];
        C[i]*=100;
    }
    for(i=1;i<=n;i++)
        fin>>T[i];
    st=0;
    dr=3e9;
    while(st<=dr)
    {
        mid=(st+dr)>>1;
        if(check(mid))
            st=mid+1;
        else
            dr=mid-1;
    }
    sol=(double) dr/100;
    fout<<fixed<<setprecision (2)<<sol;
    return 0;
}