Cod sursa(job #2049358)

Utilizator herbertoHerbert Mohanu herberto Data 27 octombrie 2017 09:13:29
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 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, p1, p2, s1, s2, intreg, rest;
  double max, s, st, dr, ans, x;
  fscanf(fin, "%d%d%d", &n, &l, &u);
  for(i=1; i<=n; i++){
    fscanf(fin, "%lf", &c[i]);
//    c[i]*=100;
  }
  for(i=1; i<=n; i++)
    fscanf(fin, "%lf", &t[i]);

  st=0; dr=30000000;
  ans=-23232323;
  ok=1;
  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;
    max=-999999999;
    for(i=1; i<=n; i++){
      if(!d.empty() && poz.front()<i-u){
        d.pop_front();
        poz.pop_front();
      }
//      printf("%d\n", d.size());
      s=s+b[i];
      while(!d.empty() && s<=d.back()){
        d.pop_back();
        poz.pop_back();
      }
//      if(x==50000000)
//        printf("%d %d", max, s-d.front());
      d.push_back(s);
      poz.push_back(i);
//      printf("%d %d %d %d\n", s, d.front(), poz.front(), i-u);
      if(!d.empty() && s-d.front()>max && i!=poz.front()){
        max=s-d.front();
        p1=poz.front();
        p2=i;

//        printf("DA");
      }
//      if(x==50000000)
//        printf("max%d posmax%d\n", max, s-d.front());
    }
    while(!d.empty()){
      d.pop_front();
      poz.pop_front();
    }
//    if(x==83)
//      printf("\n");
//    printf("%.2lf %.2lf %.2lf %.2lf\n", x, st, dr, max);
//    if(max!=-999999999){
//      s1=0; s2=0;
//      p1++;
//      for(i=p1; i<=p2; i++){
//        s2+=c[i];
//        s1+=t[i];
//      }
////      if(x==83)
////      printf("%d %d %d %d %d\n", x, p1, p2, s1, s2);
//      if(s2/s1==x){
//        ans=x;
//        ok=0;
//      }
//    }
    if(max>0)
      st=x;
    if(max<0)
      dr=x;


  }
  fprintf(fout, "%.2lf", st);
//  intreg=ans/100;
//  rest=ans%100;
//  fprintf(fout, "%d.%d", intreg, rest);
  fclose(fin);
  fclose(fout);
  return 0;
}