Pagini recente » Borderou de evaluare (job #1398045) | Cod sursa (job #2290233) | Cod sursa (job #2242637) | Cod sursa (job #2727639) | Cod sursa (job #852638)
Cod sursa(job #852638)
#include<fstream>
#include<deque>
#define MAX 1000
using namespace std;
int c[30001],t[30001];
int i,n,l,u;
double st,dr,med,m,medie;
ifstream f("secv3.in");
ofstream g("secv3.out");
int check (double med) {
double x[n+1];
double y[n+1];
x[0]=0;
int i;
for(i=1;i<=n;++i)
x[i]=x[i-1]+(double)c[i]-med*t[i];
deque<int>q;
for(i=1;i<=n;++i){
while(!q.empty() && x[q.back()]>=x[i])
q.pop_back();
q.push_back(i);
while(i-q.front()>u-l)
q.pop_front();
y[i]=x[i]-x[q.front()];
}
for(i=l;i<=n;++i){
if(x[i]-x[i-l]+y[i-l]>=0)
return 1;
}
return 0;
}
int main () {
f>>n>>l>>u;
for(i=1;i<=n;++i)
f>>c[i];
for(i=1;i<=n;++i)
f>>t[i];
st=0;
dr=MAX;
while(st<=dr) {
m=(st+dr)/2;
if(check(m)){
medie=m;
st=m+0.001;
}
else
dr=m-0.001;
}
g<<medie<<"\n";
return 0;
}