Pagini recente » Cod sursa (job #155293) | Cod sursa (job #1233665) | Cod sursa (job #1485029) | Cod sursa (job #556265) | Cod sursa (job #1537460)
#include <fstream>
#include <deque>
#define NMAX 30002
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n,c[NMAX],t[NMAX],l,u;
double dif[NMAX];
deque<int>q;
bool verif(double x)
{
for(int i=1;i<=n;i++)
dif[i]=dif[i-1]+c[i]-(t[i]*x);
q.clear();
for(int i=1;i<=n-l;i++)
{
while(!q.empty() && dif[q.back()]>=dif[i])
q.pop_back();
q.push_back(i);
while(i-q.front()==u-l+1)
q.pop_front();
if(dif[i+l]-dif[q.front()]>=0)
return 1;
}
return 0;
}
void caut()
{
double inc = 0, sf = 1000, mij;
while(inc<=sf)
{
mij = (inc+sf)/2;
if(verif(mij)) inc=mij+0.001;
else sf=mij-0.001;
}
int aux = inc*100;
fout<<aux/100<<'.'<<aux%100;
}
int main()
{
fin>>n>>l>>u;
for(int i=1;i<=n;i++)
fin>>c[i];
for(int i=1;i<=n;i++)
fin>>t[i];
caut();
return 0;
}