Cod sursa(job #916113)

Utilizator dariusdariusMarian Darius dariusdarius Data 15 martie 2013 20:23:42
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<deque>
#define eps 1.e-3
using namespace std;
int n,x,y,a[30005],b[30005];
double sp[30005];
deque<int> q;
inline bool ok(double p)
{
    int i;
    for(i=1;i<=n;i++)
        sp[i]=sp[i-1]+1.0*a[i]-p*b[i];
    while(!q.empty()) q.pop_front();
    for(i=x;i<=n;i++)
    {
        while(!q.empty() && sp[q.back()]-sp[i-x+1]>-eps)
            q.pop_back();
        q.push_back(i-x+1);
        if(i-q.front()>=y+1)
            q.pop_front();
        if(sp[i]-sp[q.front()]>=eps)
            return true;
    }
    return false;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    int i;
    scanf("%d%d%d",&n,&x,&y);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    double st,dr,med,last;
    st=0;dr=1.e9;last=0;
    while(dr-st>=eps)
    {
        med=(st+dr)*0.5;
        if(ok(med))
            last=med,st=med+eps;
        else dr=med-eps;
    }
    printf("%.2lf\n",last);
    return 0;
}