Cod sursa(job #2221273)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 13 iulie 2018 15:45:29
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream>
#include<deque>
#include<iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

int N,L,U;
pair <double, double> V[30010];
deque <pair <double, int> > Deq;

void AddDeq(pair <double,int> Nr)
{
    while(!Deq.empty() && Nr.first<Deq.back().first)
        Deq.pop_back();
    Deq.push_back(Nr);
}

void CutDeq(int Ind)
{
    while(!Deq.empty() && Deq.front().second<Ind-U)
        Deq.pop_front();
}

int Check(double K)
{
    while(!Deq.empty())
        Deq.pop_back();
    for(int i=L;i<=U;i++)
    if((V[i].first-K*V[i].second)>=0)
        return 1;
    for(int i=L+1;i<=N;i++){
        pair <double,int> X=make_pair(V[i-L].first-K*V[i-L].second,i-L);
        AddDeq(X);
        CutDeq(i);
        if((V[i].first-K*V[i].second)>=Deq.front().first)
            return 1;
    }
    return 0;
}

double Cautbin()
{
    double Left=0,Right=1003,Sol=0,Mid;
    while(Left<=Right){
          Mid=(Left+Right)/2;
          if(Check(Mid)){
              Sol=Mid;
              Left=Mid+0.0001;
          }
          else Right=Mid-0.0001;
    }
    return Sol;
}

int main()
{
    fin>>N>>L>>U;
    fin>>V[1].first;
    for(int i=2;i<=N;i++){
        double X;
        fin>>X;
        V[i].first=V[i-1].first+X;
    }
    fin>>V[1].second;
    for(int i=2;i<=N;i++){
        double X;
        fin>>X;
        V[i].second=V[i-1].second+X;
    }
    fout<<setprecision(2)<<Cautbin()<<'\n';
}