Cod sursa(job #2838464)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 23 ianuarie 2022 18:13:26
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque <int>dx;
int c[30005], t[30005], n, l, u;
double aux[30005], s[30005];
int verif(double m)
{
    double minn=0;
    dx.clear();
    for(int i=1; i<=n; i++)
    {
        aux[i]=(double)c[i]-m*t[i];
        s[i]=s[i-1]+aux[i];
    }
    for(int i=l; i<=n; i++)
    {
        while(!dx.empty() && s[i-l+1]<=s[dx.back()])
            dx.pop_back();
        dx.push_back(i-l+1);
        if(i-dx.front()+1>u)  dx.pop_front();
        if(s[i]-s[dx.front()]>=0 && (i!=dx.front() || s[i]>=0)) return 1;
    }
    return 0;
}
int main()
{
    fin >> n >> l >> u;
    double mnn=0;
    for(int i=1; i<=n; i++)   fin >> c[i];
    for(int i=1; i<=n; i++)   fin >> t[i];
    double st=0.001, dr=30000.0, ok=0;
    while(dr-st>0.01)
    {
        double mij=(st+dr)/2;
        if(verif(mij))
        {
            ok=mij; st=mij+0.01;
        }
        else dr=mij-0.01;
    }
    fout << fixed << setprecision(2) << ok;
    return 0;
}