Cod sursa(job #1469589)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 8 august 2015 20:15:08
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <deque>
#include <utility>
#include <algorithm>

#define st first
#define nd second
#define mp make_pair
#define ppb pop_back
#define ppf pop_front
#define psb push_back
#define psf push_front

using namespace std;

const int NM = 30005;

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

double Div(int Cost,int Timp)
{
    return (double(Cost) / double(Timp));
}

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

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

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

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

     int Cost = 0,Timp = 0;

     for (int i = 1;i <= N;i++)
     {
         D.psb(i);
         Cost += C[i];
         Timp += T[i];

         if (D.size() > U)
            Cost -= C[D.front()],Timp -= T[D.front()],D.ppf();

         if (D.size() >= L)
             Sol = max(Sol,Div(Cost,Timp));

         while(D.size() > 1 && Div(Cost - C[D.front()],Timp - T[D.front()]) > Div(Cost,Timp) && (N - i >= L - D.size() + 1))
         {
             Cost -= C[D.front()];
             Timp -= T[D.front()];
             D.ppf();

             if (D.size() >= L)
                Sol = max(Sol,Div(Cost,Timp));
         }
     }

     printf("%.2f",Sol);
   return 0;
}