Cod sursa(job #1471500)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 14 august 2015 10:20:03
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000;
const int NM = 30005;

int N,L,U,K;
int C[NM],T[NM];
double Sol;
double Df[NM];
deque< int > D;

bool Check(double X)
{
    for (int i = 1;i <= N;i++)
        Df[i] = Df[i - 1] + C[i] - (T[i] * X);

    D.clear();

    for (int i = 0;i <= N - L;i++)
    {
        while (!D.empty() && Df[D.back()] >= Df[i])
              D.pop_back();

        D.push_back(i);

        //if (i < K) continue;

        while (i - D.front() == K)
           D.pop_front();

        if (Df[i + L] - Df[D.front()] >= 0)
           return 1;
    }

    return 0;
}

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);

     scanf("%d %d %d",&N,&L,&U);

     K = U - L + 1;

     for (int i = 1;i <= N;i++)
         scanf("%d",&C[i]);

     for (int i = 1;i <= N;i++)
         scanf("%d",&T[i]);

     double First = 0,Last = INF;

     while(First <= Last)
     {
         double Middle = (First + Last) / 2.0;

         if (Check(Middle))
            First = Middle + 0.001;
        else
            Last = Middle - 0.001;
     }

     Sol = First - 0.001;

     printf("%.3f\n",Sol);

   return 0;
}