Cod sursa(job #1528910)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 20 noiembrie 2015 10:59:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<cstdio>
#include<queue>
using namespace std;
int c[30010],t[30010],l,u,n;
double diff[30010];
deque<int> q;
int verify(double x){
    int i;
    q.clear();
    for(i=1;i<=n;i++)
        diff[i]=diff[i-1]+c[i]-(t[i]*x);
    for(i=1;i<=n-l;i++){
        while(!q.empty()&&diff[q.back()]>=diff[i])
            q.pop_back();
        q.push_back(i);
        while(i-q.front()==u-l+1)
            q.pop_front();
        if(diff[i+l]-diff[q.front()]>=0)
            return 1;
    }
    return 0;
}
int main(){
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    int i,j;
    double l1=0,l2=100000,m;
    double answer;
    scanf("%d%d%d",&n,&l,&u);
    for(i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&t[i]);
    while(l1<=l2){
        m=(l1+l2)/2.0;
        if(verify(m)==1)
            l1=m+0.001;
        else
            l2=m-0.001;
    }
    answer=l1-0.001;
    printf("%.3f",answer);
    return 0;
}