Cod sursa(job #1893663)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 25 februarie 2017 21:14:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia14-cautare_binara Marime 1.24 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#define MaxN 30001
#define INF 2000000000
#define time second
#define value first
#define var 0.001
using namespace std;
 
pair <int,int> v[MaxN];
int N,U,L;
double S[MaxN]={},lw,hi,mid,Sol;
deque <int>D;
bool Verify(double val)
{
    for(int i=1;i<=N;i++)
        S[i]=S[i-1]+v[i].value-v[i].time*val;
    double Max=-INF;
    D.clear();
    for(int i=L;i<=N;i++)
    {
        while(!D.empty()&&S[D.back()]>=S[i-L])
            D.pop_back();
        D.push_back(i-L);
        while(D.front()<=i-U)
            D.pop_front();
        if(Max<S[i]-S[D.front()])
            Max=S[i]-S[D.front()];
    }
    if(Max>=0)
        return true;
    else return false;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&N,&L,&U);
    v[0].value=v[0].time=0;
    for(int i=1;i<=N;i++)
        scanf("%d",&v[i].value);
    for(int i=1;i<=N;i++)
        scanf("%d",&v[i].time);
    lw=0,hi=1001,mid;
    while(lw<=hi)
    {
        mid=(lw+hi)/2;
        if(Verify(mid))
        {
            Sol=mid;
            lw=mid+var;
        }
        else hi=mid-var;
    }
    printf("%lf",Sol);
    return 0;
}