Cod sursa(job #1716716)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 13 iunie 2016 16:09:50
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline int nextnum(){
    int a=0;
    char c=nextch();
    while(c<'0' || c>'9')
        c=nextch();
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a;
}

int n, l, r;
double a[30001], b[30001];
int dq[30001];
double s[30001];
int x, y;

inline int ok(double e){
    int st, dr;
    s[0]=0.0;
    st=dr=0;
    for(int 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 && s[i]-s[dq[st]]>-0.00000001)
            return 1;
    }
    return 0;
}

int main(){
    FILE*fo;
    fi=fopen("secv3.in","r");
    fo=fopen("secv3.out","w");
    fscanf(fi,"%d%d%d", &n, &l, &r);
    for(int i=1;i<=n;i++)
        fscanf(fi,"%lf", &a[i]);
    for(int i=1;i<=n;i++)
        fscanf(fi,"%lf", &b[i]);
    double st=-1000.0, dr=1000.0;
    while(dr-st>0.001){
        double m=(st+dr)/2;
        if(ok(m))
            st=m;
        else
            dr=m-0.001;
    }
    printf("%d ", ok(0.8));
    if(ok(st))
        fprintf(fo,"%.2lf", st);
    else{
        fprintf(fo,"%.2lf", dr);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}