Pagini recente » Cod sursa (job #2292324) | Cod sursa (job #1004656) | Cod sursa (job #1835356) | Cod sursa (job #1065930) | Cod sursa (job #976516)
Cod sursa(job #976516)
#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;
}