Cod sursa(job #1992421)

Utilizator dragos231456Neghina Dragos dragos231456 Data 20 iunie 2017 14:17:50
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#define N 30005
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
double timp[N],cost[N],rez;
int n,l,u;
deque<int> pos;

double curent(int i)
{
    return ((cost[i]-cost[pos.front()])/(timp[i]-timp[pos.front()]));
}

bool cond(int i)
{
    return (curent(i)>curent(pos.back()));
}

void citire()
{
    for(int i=1;i<=n;++i)
    {
        f>>cost[i];
        cost[i]+=cost[i-1];
    }
    for(int i=1;i<=n;++i)
    {
        f>>timp[i];
        timp[i]+=timp[i-1];
    }
}

int main()
{
    f>>n>>l>>u;
    citire();
    for(int i=1;i<l;++i)
    {
        pos.push_back(i);
    }
    pos.push_front(0);
    for(int i=l;i<=n;++i)
    {
        if(!pos.empty() && i-pos.front()>u)
        {
            pos.pop_front();
        }
        while(!pos.empty() && cond(i) && i-pos.back()<=u-l)
        {
            pos.pop_back();
        }
        rez=max(rez,curent(i));
        pos.push_back(i);
    }
    g<<rez;
    return 0;
}