Cod sursa(job #976516)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 23 iulie 2013 13:22:12
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
struct Element{
double cost;
double time;
};
Element Partial[30002];
int N,L,U;
int Deque[30002];
double maximum;
void Read()
{
    int i;
    double value;
    f>>N>>L>>U;
    for(i=1;i<=N;i++)
    {
        f>>value;
        Partial[i].cost=Partial[i-1].cost+value;
    }
    for(i=1;i<=N;i++)
    {
        f>>value;
        Partial[i].time=Partial[i-1].time+value;
        if(maximum<Partial[i].cost/Partial[i].time && i<=U && i>=L)
            maximum=Partial[i].cost/Partial[i].time;
    }
}
bool compare(Element x,Element y)
{
    double dif1,dif2;
    dif1=x.cost-y.cost;
    dif2=x.time-y.time;
    if(dif1>0)
    {
        if(dif2<0)
            return 0;
        else
        {
            if(dif2>dif1)
                return 1;
            if(dif2<dif1)
                return 0;
            if(dif2==dif1)
                return x.cost<y.cost;
        }
    }
    if(dif1<0)
    {
        if(dif2>0)
            return 1;
        else
        {
            if(dif2>dif1)
                return 0;
            if(dif2<dif1)
                return 1;
            if(dif2==dif1)
                return x.cost<y.cost;
        }
    }
}
void Solve()
{
    int i;
    int End=0,Begin=1;
    for(i=L+1;i<=N;i++)
    {
        while(End>=Begin && compare(Partial[i-L],Partial[Deque[End]])==1)
            End--;
        Deque[++End]=i-L;
        if(Deque[Begin]==i-U-1)
            Begin++;
        if(maximum<(Partial[i].cost-Partial[Deque[Begin]].cost)/(Partial[i].time-Partial[Deque[Begin]].time))
            maximum=(Partial[i].cost-Partial[Deque[Begin]].cost)/(Partial[i].time-Partial[Deque[Begin]].time);
    }
    g<<fixed<<setprecision(2)<<maximum<<"\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}