Cod sursa(job #1068406)

Utilizator Barcau_EmanuelBarcau Emanuel Barcau_Emanuel Data 28 decembrie 2013 12:28:30
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
#include<deque>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,L,U,cost[30100],timp[30100];
double v[30100],sum[30100];
deque <int> D;

inline bool Posibil(double X)
{
    int i;
    double best=-2000000000.0;
    sum[0]=0.0;
    for(i=1;i<=n;i++)
    {
        v[i]=1.0*cost[i]-1.0*timp[i]*X;
        sum[i]=sum[i-1]+v[i];
    }
    D.clear();
    for(i=L;i<=n;i++)
    {
        while(D.size() && sum[D.back()]>=sum[i-L])
            D.pop_back();
        D.push_back(i-L);
        while(D.front()<i-U)
            D.pop_front();
        best=max(best,sum[i]-sum[D.front()]);
    }
    if(best>=0.0)
        return true;
    return false;
}

inline double CautareBinara()
{
    double st,dr,mij,rez=0.0;
    st=0.0;
    dr=1000.0;
    while(dr-st>0.001)
    {
        mij=(st+dr)/2.0;
        if(Posibil(mij))
        {
            rez=mij;
            st=mij;
        }
        else
            dr=mij;
    }
    return rez;
}

int main()
{
    int i;
    ifstream fin("secv3.in");
    fin>>n>>L>>U;
    for(i=1;i<=n;i++)
        fin>>cost[i];
    for(i=1;i<=n;i++)
        fin>>timp[i];
    fin.close();

    freopen("secv3.out","w",stdout);
    printf("%.3lf\n",CautareBinara());
    return 0;
}