Cod sursa(job #1471406)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 13 august 2015 19:04:47
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

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

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

    D.clear();

    for (int i = 1;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]),C[i] *= 100;

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

     int First = 0,Last = INF;

     while(First <= Last)
     {
         int Middle = (First + Last) >> 1;

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

     Sol = First - 1;

     printf("%.2f",1.0 * Sol / 100);

   return 0;
}