Cod sursa(job #1064088)

Utilizator hevelebalazshevele balazs hevelebalazs Data 21 decembrie 2013 14:40:34
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#include <queue>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 30000
int mn,mx,k,n,a[N],b[N];

bool Q(double x){
    double si=0,sj=0,sl=0;
    fr(i,0,mn-1)si+=a[i]-x*b[i];
    std::deque<double>q;
    fr(i,mn-1,n){
        si+=a[i]-x*b[i];
        int j=i-mn;
        sj+=a[j]-x*b[j];
        int l=j-k;
        if(l>=0) sl+=a[l]-x*b[l];
        while(!q.empty()&&q.front()>sj) q.pop_front();
        q.push_front(sj);
        if(j>=k-1&&q.back()==sl) q.pop_back();
        if(si-q.back()>=0)return true;
        }
    return false;
    }

int main(){
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%i%i%i",&n,&mn,&mx);
    k=mx-mn+1;
    fr(i,0,n)scanf("%i",a+i);
    fr(i,0,n)scanf("%i",b+i);
    double l=0,r=1000;
    while(r-l>=0.001){
        double c=(l+r)/2;
        if(Q(c)) l=c;
        else r=c;
        }
    printf("%.2f",(l+r)/2);
    return 0;
    }