Cod sursa(job #990928)

Utilizator assa98Andrei Stanciu assa98 Data 29 august 2013 12:29:10
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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(sp[i]-sp[Q.front()]>0)
            return true;

        while(!Q.empty()&&sp[i]<=sp[Q.back()])
            Q.pop_back();
        Q.push_back(i);
    }
    return false;
}

double bsearch(double st,double dr) {
    double ans;
    while(st<dr) {
        double mij=(st+dr)/2.0;
        //fprintf(stderr,"%d ",mij);
        if(check(mij)) {
            st=mij;
            ans=mij;
        }
        else
            dr=mij-err;
    }
    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,30000000.00));
    return 0;
}