Cod sursa(job #2040430)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 15 octombrie 2017 19:43:01
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
int n,l,u,vCost[30005],vTimp[30005];
double vAux[30005];
deque <int>d;
void citire()
{
    int aux;
    scanf("%d%d%d",&n,&l,&u);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&aux);
        vCost[i]=vCost[i-1]+aux;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&aux);
        vTimp[i]=vTimp[i-1]+aux;
    }
}
bool verificare(double elemDeVerificat)
{
    for(int i=1;i<=n;i++)
    {
        vAux[i]=vCost[i]-(double)vTimp[i]*elemDeVerificat;
    }
    while(!d.empty())
        d.pop_back();
    for(int i=1;i<=n;i++)
    {
        while(!d.empty()&&vAux[d.back()]>=vAux[i])
            d.pop_back();
        d.push_back(i);
        if(i-d.front()==u-l+1)
            d.pop_front();

        if(i+l<=n&&vAux[i+l]-vAux[d.front()]>0)
            return true;
    }
    return false;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    citire();
    double st=0,dr=0x3f3f3f3f,mij;
    while(dr-st>=0.001)
    {
        mij=(st+dr)/2;
        if(verificare(mij)) st=mij;
        else dr=mij;
    }
    printf("%lf",st);
    return 0;
}