Cod sursa(job #983273)

Utilizator smaraldaSmaranda Dinu smaralda Data 11 august 2013 13:50:12
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<math.h>
#include<deque>
#define NMAX 30000
#define eps 1.e-14
using namespace std;

struct DEQUE { int pos; double val; };
deque <DEQUE> dq;

int n,lo,hi,cost[NMAX+5],timp[NMAX+5];
double v[NMAX+5],sp[NMAX+5];

DEQUE make (int a, double b) {
    DEQUE ret={a,b};
    return ret;
}

int comp (double a, double b) {
    if(fabs(a-b)<eps)
        return 0;
    if(a-b>=eps)
        return 1;
    return -1;
}

bool check (double val) {
    int i;
    double sum;
    DEQUE aux;
    while(!dq.empty())
        dq.pop_back();
    for(i=1;i<=n;i++) {
        v[i]=cost[i]-(double)val*timp[i];
        sp[i]=sp[i-1]+v[i];
        }

    sum=-2000000000;
    dq.push_back(make(0,0));
    for(i=0;i<=n-lo;i++) {
        if(!dq.empty() && dq.front().pos < i+lo-hi)
            dq.pop_front();
        while(!dq.empty() && comp(dq.front().val,sp[i]) > 0)
            dq.pop_back();
        dq.push_back(make(i,sp[i]));
        if(comp(sp[i+lo] - dq.front().val , sum) > 0)
            sum=sp[i+lo]-dq.front().val;
        }
    return comp(sum,0) > 0;
}

double bs (double left, double right) {
    double last,mid;
    while(right-left>-eps) {
        mid=(left+right)*0.5;
        if(check(mid)) {
            last=mid;
            left=mid+0.01;
            }
        else
            right=mid-0.01;
        }
    return last;
}

int main() {
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&n,&lo,&hi);

    for(int i=1; i <= n ; i++)
        scanf("%d",&cost[i]);
    for(int i=1; i<= n; i++)
        scanf("%d",&timp[i]);

    printf("%.2lf\n",bs(0,30000000));
    return 0;
}