Cod sursa(job #2049378)

Utilizator herbertoHerbert Mohanu herberto Data 27 octombrie 2017 09:22:29
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<stdio.h>
#include<stdlib.h>
#include<deque>
using namespace std;
#define MAXN 30001

deque <double> d;
deque <int> poz;

double c[MAXN], t[MAXN], b[MAXN];
int main(){
  FILE*fin=fopen("secv3.in", "r");
  FILE*fout=fopen("secv3.out", "w");
  int n, a, l, u, i, ok;
  double max, s, st, dr, x;
  fscanf(fin, "%d%d%d", &n, &l, &u);
  for(i=1; i<=n; i++)
    fscanf(fin, "%lf", &c[i]);
  for(i=1; i<=n; i++)
    fscanf(fin, "%lf", &t[i]);

  st=0; dr=30000000;
  while(dr-st>=0.001){
    x=(st+dr)/2;
//    if(x==83)
//    printf("\n");
    for(i=1; i<=n; i++){
      b[i]=c[i]-x*t[i];
//      if(x==83)
//      printf("%d ", b[i]);
    }
//    if(x==83)
//    printf("\n");
    s=0;
    ok=0;
    for(i=1; i<=n; i++){
      if(!d.empty() && poz.front()<i-u){
        d.pop_front();
        poz.pop_front();
      }
      s=s+b[i];
      while(!d.empty() && s<=d.back()){
        d.pop_back();
        poz.pop_back();
      }
      d.push_back(s);
      poz.push_back(i);
      if(!d.empty() && s-d.front()>0 && i!=poz.front())
        ok=1;

    }
    while(!d.empty()){
      d.pop_front();
      poz.pop_front();
    }
    if(ok)
      st=x;
    else
      dr=x;


  }
  fprintf(fout, "%.2lf", st);
  fclose(fin);
  fclose(fout);
  return 0;
}