Cod sursa(job #1904709)

Utilizator cella.florescuCella Florescu cella.florescu Data 5 martie 2017 18:56:23
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia15-ev_p_s_q_dq_dp Marime 1.14 kb
#include <cstdio>

#include <deque>

using namespace std;

const int MAXN = 30000;
const double EPS = 0.001;

int c[MAXN + 1], t[MAXN + 1];
double v[MAXN + 1];
deque <int> deq;

int max_subarr(double x, int l, int u, int n) {
  double maxim = 0.0;
  for (int i = 1; i <= n; ++i)
    v[i] = v[i - 1] + 1.0*c[i] - x*t[i];
  deq.clear();
  for (int i = l; i <= n; ++i) {
    if (deq.front() == i - u - 1)
      deq.pop_front();
    while (deq.empty() == 0 && v[deq.back()] > v[i - l + 1])
      deq.pop_back();
    deq.push_back(i - l + 1);
    if (v[i] - v[deq.front()] > 0)
      return 1;
  }
  return 0;
}

int main()
{
    FILE *fin, *fout;
    double step, ans;
    int n, l, u, i;
    fin = fopen("secv3.in", "r");
    fscanf(fin, "%d%d%d", &n, &l, &u);
    for (i = 1; i <= n; ++i)
      fscanf(fin, "%d", c + i);
    for (i = 1; i <= n; ++i)
      fscanf(fin, "%d", t + i);
    fclose(fin);
    for (ans=0.0, step = (1<<9); step > EPS; step /= 2.0)
      if (max_subarr(ans + step, l, u, n))
        ans += step;
    fout = fopen("secv3.out", "w");
    fprintf(fout, "%lf\n", ans);
    fclose(fout);
    return 0;
}