Cod sursa(job #1537460)

Utilizator horiainfoTurcuman Horia horiainfo Data 27 noiembrie 2015 13:03:29
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <deque>
#define NMAX 30002
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");

int n,c[NMAX],t[NMAX],l,u;
double dif[NMAX];
deque<int>q;

bool verif(double x)
{
    for(int i=1;i<=n;i++)
        dif[i]=dif[i-1]+c[i]-(t[i]*x);
    q.clear();

    for(int i=1;i<=n-l;i++)
    {
        while(!q.empty() && dif[q.back()]>=dif[i])
            q.pop_back();
        q.push_back(i);
        while(i-q.front()==u-l+1)
            q.pop_front();
        if(dif[i+l]-dif[q.front()]>=0)
            return 1;
    }
    return 0;
}
void caut()
{
    double inc = 0, sf = 1000, mij;
    while(inc<=sf)
    {
        mij = (inc+sf)/2;
        if(verif(mij)) inc=mij+0.001;
        else    sf=mij-0.001;
    }
    int aux = inc*100;
    fout<<aux/100<<'.'<<aux%100;
}
int main()
{
    fin>>n>>l>>u;
    for(int i=1;i<=n;i++)
        fin>>c[i];
    for(int i=1;i<=n;i++)
        fin>>t[i];
    caut();
    return 0;
}