Cod sursa(job #1560250)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 12:27:28
Problema Secventa 3 Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define MAXN 30000
int c[MAXN], t[MAXN], dq[MAXN];
double sum[MAXN];

inline char bun(double x, int n, int l, int r){
  int i, st = 0, dr = 1;
  dq[0] = 0;
  sum[0] = c[0] - x * t[0];
  if(l == 1 && sum[0] >= 0)
    return 1;
  for(i = 1; i < n; i++){
    sum[i] = sum[i - 1] + c[i] - x * t[i];
    if(i - dq[st] + 1 > r)
      st++;
    if(sum[i] - sum[dq[st]] >= 0)
      return 1;
    while(dr > st && sum[i] < sum[dq[dr - 1]])
      dr--;
    dq[dr] = i;
    dr++;
  }
  return 0;
}

int main(){
  FILE *in = fopen("secv3.in", "r");
  int n, l, r, i;
  fscanf(in, "%d%d%d", &n, &l, &r);
  for(i = 0; i < n; i++)
    fscanf(in, "%d", &c[i]);
  for(i = 0; i < n; i++)
    fscanf(in, "%d", &t[i]);
  fclose(in);
  double rez = 0, pas;
  for(pas = (double)(1 << 9); pas > 0.001; pas /= 2){
    if(bun(rez + pas, n, l, r))
      rez += pas;
  }
  FILE *out = fopen("secv3.out", "w");
  fprintf(out, "%.2lf", rez);
  fclose(out);
  return 0;
}