Cod sursa(job #1364522)

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

int c[MAX+1];
int t[MAX+1];
long long 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]=(long long)c[i]-(long long)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 0;
}


int cb(){
    int pas,m;

    pas=1<<17;
    m=0;
    while(pas>0){
        if (verif(m+pas)==1) m+=pas;
        pas/=2;
    }

    return m;
}


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

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

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

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