Cod sursa(job #993059)

Utilizator assa98Andrei Stanciu assa98 Data 3 septembrie 2013 10:21:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

const double eps=1e-6;

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

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

double bsearch(double st,double dr) {
    double ans;
    for(int stp=0;stp<60;++stp) {
        double mij=(double)(st+dr)/2.0;
        if(check(mij))
            st=mij;
        else
            dr=mij;
    }
    return st;
}

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.0,30000000.0));
    return 0;
}