Pagini recente » Cod sursa (job #1973700) | Cod sursa (job #1159502) | Cod sursa (job #1001850) | Cod sursa (job #536376) | Cod sursa (job #2221277)
#include<fstream>
#include<deque>
#include<iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int N,L,U;
pair <double, double> V[30010];
deque <pair <double, int> > Deq;
void AddDeq(pair <double,int> Nr)
{
while(!Deq.empty() && Nr.first<Deq.back().first)
Deq.pop_back();
Deq.push_back(Nr);
}
void CutDeq(int Ind)
{
while(!Deq.empty() && Deq.front().second<Ind-U)
Deq.pop_front();
}
int Check(double K)
{
while(!Deq.empty())
Deq.pop_back();
for(int i=L;i<=U;i++)
if((V[i].first-K*V[i].second)>=0)
return 1;
for(int i=L+1;i<=N;i++){
pair <double,int> X=make_pair(V[i-L].first-K*V[i-L].second,i-L);
AddDeq(X);
CutDeq(i);
if((V[i].first-K*V[i].second)>=Deq.front().first)
return 1;
}
return 0;
}
double Cautbin()
{
double Left=0,Right=1003,Sol=0,Mid;
while(Left<=Right){
Mid=(Left+Right)/2;
if(Check(Mid)){
Sol=Mid;
Left=Mid+0.0001;
}
else Right=Mid-0.0001;
}
return Sol;
}
int main()
{
fin>>N>>L>>U;
fin>>V[1].first;
for(int i=2;i<=N;i++){
double X;
fin>>X;
V[i].first=V[i-1].first+X;
}
fin>>V[1].second;
for(int i=2;i<=N;i++){
double X;
fin>>X;
V[i].second=V[i-1].second+X;
}
fout<<setprecision(3)<<fixed<<Cautbin()<<'\n';
}