Cod sursa(job #1728811)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 13 iulie 2016 18:39:56
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <cstring>
#define MAXN 30000
double cost[MAXN+1],timp[MAXN+1],v[MAXN+1];
int deq[MAXN+1];
int n,l,u;
inline char cauta(double medie){
    int i,b,e;
    double max=-1000000000;
    for(i=1;i<=n;i++){
       v[i]=cost[i]-medie*timp[i];
       v[i]+=v[i-1];
    }
    memset(deq,0,sizeof(deq));
    b=0;
    e=-1;
    for(i=1;i<=n;i++){
        if(deq[b]<i-u)
          b++;
        if(i-l>=0){
          while(e>=b&&v[i-l]<=v[deq[e]])
             e--;
          deq[++e]=i-l;
        }
        if(v[i]-v[deq[b]]>max)
            max=v[i]-v[deq[b]];
    }
    return (max>=0);
}
int main(){
    FILE*fi,*fout;
    int i;
    double rez,pas,EPS;
    fi=fopen("secv3.in" ,"r");
    fout=fopen("secv3.out" ,"w");
    fscanf(fi,"%d%d%d" ,&n,&l,&u);
    EPS=0.0000001;
    for(i=1;i<=n;i++)
      fscanf(fi,"%lf" ,&cost[i]);
    for(i=1;i<=n;i++)
      fscanf(fi,"%lf" ,&timp[i]);
    pas=1;
    for(i=1;i<=12;i++)
      pas*=2;
    rez=0;
    for(;pas>EPS;pas/=2)
      if(cauta(rez+pas)==1)
        rez+=pas;
    fprintf(fout,"%lf" ,rez);
    fclose(fi);
    fclose(fout);
    return 0;
}