Pagini recente » Cod sursa (job #1932522) | Borderou de evaluare (job #888920) | Cod sursa (job #2411009) | Cod sursa (job #644303) | Cod sursa (job #659561)
Cod sursa(job #659561)
#include <fstream>
#include <iomanip>
#include <deque>
#define nmax 30002
using namespace std;
int n, L, U, a[nmax], b[nmax];
double v[nmax], s[nmax];
deque<int> dq;
double sol;
ifstream f("secv3.in");
ofstream g("secv3.out");
void citeste(){
f>>n>>L>>U;
for(int i=1; i<=n; ++i) f>>a[i];
for(int i=1; i<=n; ++i) f>>b[i];
}
int rezolva(double x){
dq.clear();
for(int i=1; i<=n; ++i){
s[i] = s[i-1] + a[i] - x*b[i];
}
for(int i=L; i<=n; ++i){
while(!dq.empty() && s[i-L+1] <= s[ dq.back() ] ) dq.pop_back();
dq.push_back(i-L);
while ( i - U - 1 >= dq.front()) dq.pop_front();
//d[i] = dq.front();
if (s[i] - s[dq.front()] >= 0) return 1;
}
return 0;
}
void bs(){
double st = 0;
double dr = 10000000;
while(dr - st > 0.0001){
double mij = (st + dr) / 2;
if (rezolva(mij)){
sol = mij;
st = mij+0.0001;
}else dr = mij - 0.0001;
}
g<<setprecision(3)<<sol<<"\n";
}
int main(){
citeste();
bs();
f.close();
g.close();
return 0;
}