Pagini recente » Cod sursa (job #956809) | Cod sursa (job #2641230) | Cod sursa (job #1540368) | Cod sursa (job #2569633) | Cod sursa (job #432910)
Cod sursa(job #432910)
#include<fstream>
#include<math.h>
#include<deque>
#define nmax 30100
using namespace std;
int c[nmax],t[nmax];
double a[nmax],b[nmax];
double st,dr=1000,m,sol;
int q;
int main()
{
int n,l,u,k,i,gasit=0;
ifstream read ("secv3.in");
ofstream write ("secv3.out");
read>>n>>l>>u;
k=u-l+1;
for(i=1;i<=n;i++)
read>>c[i];
for(i=1;i<=n;i++)
read>>t[i];
while(!gasit)
{
q++;
deque <int> dq;
m=(st+dr)/2;
for(i=1;i<=n;i++)
a[i]=a[i-1]+c[i]-m*t[i];
dq.push_back(0);
for(i=1;i<=n;i++)
{
while(!dq.empty()&&dq.front()+k<i+1)
dq.pop_front();
while(!dq.empty()&&a[dq.back()]>a[i])
dq.pop_back();
dq.push_back(i);
b[i]=a[dq.front()];
}
sol=-(1<<30);
for(i=1;i<=n;i++)
if(a[i]-b[i-l]>sol)
sol=a[i]-b[i-l];
if(fabs(sol)<=0.001)
gasit=1;
else
if(sol<0)
dr=m;
else
st=m;
}
write<<m;
return 0;
}