Cod sursa(job #1364392)

Utilizator livliviLivia Magureanu livlivi Data 27 februarie 2015 17:23:21
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#define MAX 30000
using namespace std;

int c[MAX+1];
int t[MAX+1];
int sp[MAX+1];
int deque[MAX+1];
int n,l,u;
int le,ri;

int verif(int m){
    int i;

    for(i=1;i<=n;i++){
        sp[i]=c[i]-m*t[i];
        sp[i]+=sp[i-1];
    }

    le=0;
    ri=1;
    deque[0]=0;
    for(i=l;i<=n;i++){
        while(ri>0 &&sp[deque[ri-1]]>=sp[i-l])
            ri--;
        deque[ri]=i-l;
        ri++;

        if (deque[le]==i-u-1) le++;

        if (sp[i]>=sp[deque[le]]) return 1;
    }

    return -1;
}


int cb(int dr){
    int st,m;

    st=0;
    while(st<dr){
        m=(st+dr)/2;

        if (verif(m)<0) dr=m;
        else st=m+1;
    }

    return st-1;
}


int main(){
    freopen ("secv3.in","r",stdin);
    freopen ("secv3.out","w",stdout);
    int i;
    int max,s;

    scanf ("%d%d%d",&n,&l,&u);

    s=0;
    for(i=1;i<=n;i++){
        scanf ("%d",&c[i]);
        c[i]*=100;
        s+=c[i];
    }
    for(i=1;i<=n;i++)
        scanf ("%d",&t[i]);

    max=cb(s);
    printf ("%d.",max/100);
    max%=100;
    if (max<10) printf ("0");
    printf ("%d",max);
    return 0;
}