Cod sursa(job #990947)

Utilizator assa98Andrei Stanciu assa98 Data 29 august 2013 12:49:46
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

const double err=0.01;

int n;
int L,U;
int a[30100];
int b[30100];

bool check(double x) {
    double v[30100];
    double sp[30100];
    
    deque<int> Q;
    
    for(int i=1;i<=n;i++) {
        v[i]=(double)a[i]-(double)b[i]*x;
        sp[i]=sp[i-1]+v[i];
    }
    
    Q.push_back(0);
    for(int i=L;i<=n;i++) {
        while(!Q.empty()&&i-Q.front()>=U)
            Q.pop_front();
        if(!Q.empty())
            if(sp[i]-sp[Q.front()]>0)
                return true;
    
        while(!Q.empty()&&sp[i-L+1]<=sp[Q.back()])
            Q.pop_back();
        Q.push_back(i-L+1);
    }
    return false;
}

double bsearch(int st,int dr) {
    double ans;
    while(st<dr) {
        double mij=(double)(st+dr)/200.0;
        //fprintf(stderr,"%d ",mij);
        if(check(mij)) {
            st=((st+dr)>>1)+1;
            ans=mij;
        }
        else
            dr=((st+dr)>>1)-1;
    }
    return ans;
}

int main() {
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&n,&L,&U);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    printf("%.2lf ",bsearch(0,(1<<30)));
    return 0;
}