Pagini recente » Cod sursa (job #2297639) | Monitorul de evaluare | Cod sursa (job #1681302) | Cod sursa (job #2476151) | Cod sursa (job #1289403)
#include<stdio.h>
#include<algorithm>
#include<deque>
#define NMAX 5000007
#define LL long long
#define INF 1000000000
using namespace std;
deque < int > Deq;
int n, L, U;
int a[NMAX], b[NMAX];
double Sum[NMAX];
int check(double med){
Sum[0] = 0;
Deq.clear();
double Ans = - INF;
for(int i = 1; i <= n; ++ i)
Sum[i] = (double) Sum[i - 1] + a[i] - med * b[i];
for(int i = L; i <= n; ++ i){
if(! Deq.empty())
Ans = max(Ans, Sum[i] - Sum[Deq.front()]);
while(! Deq.empty() && Sum[Deq.back()] >= Sum[i - L + 1])
Deq.pop_back();
Deq.push_back(i - L + 1);
if(Deq.front() + U == i)
Deq.pop_front();
}
return Ans > 0;
}
double cb(){
int st = 1, dr = (1 << 30);
double med, last = -1;
while(st <= dr){
med = (double) (st + dr) / 200.0;
if(check(med) == 1){
st = ((st + dr) >> 1) + 1;
last = med;
}
else
dr = ((st + dr) >> 1) - 1;
}
return last;
}
int main(){
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
LL Ans = -10000000000000;
scanf("%d %d %d", &n, &L, &U);
for(int i = 1; i <= n; ++ i)
scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i)
scanf("%d", &b[i]);
printf("%.2f", cb());
return 0;
}