Cod sursa(job #1522936)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 12 noiembrie 2015 10:23:45
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <cctype>
#define EPS 0.00000001
#define BUF_SIZE 4096
#define MAXN 30000
int pos=BUF_SIZE, n, l, r, dq[MAXN], a[MAXN+1], b[MAXN+1];
char buf[BUF_SIZE];
double s[MAXN+1];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
inline bool ok(double e){
    int st, dr, i;
    s[0]=0;
    st=0;
    dr=0;
    for(i=1; i<=n; i++){
        s[i]=s[i-1]+a[i]-b[i]*e;
        if((st<dr)&&(i-dq[st]>r)){
            st++;
        }
        if(i>=l){
            while((st<dr)&&(s[dq[dr-1]]>s[i-l])){
                dr--;
            }
            dq[dr++]=i-l;
        }
        if(st<dr){
            if(s[i]-s[dq[st]]>-EPS){
                return true;
            }
        }
    }
    return false;
}
int main(){
    int i;
    double rez, pas;
    FILE *fout;
    fin=fopen("secv3.in", "r");
    fout=fopen("secv3.out", "w");
    n=read();
    l=read();
    r=read();
    for(i=1; i<=n; i++){
        a[i]=read();
    }
    for(i=1; i<=n; i++){
        b[i]=read();
    }
    i=ok(0.83);
    printf("%d\n", i);
    rez=0;
    i=1<<9;
    for(pas=i; pas>0.001; pas*=0.5){
        if(ok(rez+pas)){
            rez+=pas;
        }
    }
    fprintf(fout, "%lf\n", rez);
    fclose(fin);
    fclose(fout);
    return 0;
}