Cod sursa(job #1560324)

Utilizator hrazvanHarsan Razvan hrazvan Data 2 ianuarie 2016 15:45:50
Problema Secventa 3 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#define MAXN 30000
#define EPS 0.0000001
int c[MAXN], t[MAXN], dq[MAXN];
double sum[MAXN];

inline int eq(double a, double b){
  if(a - b > EPS)
    return 1;
  if(b - a > EPS)
    return -1;
  return 0;
}

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