Pagini recente » Cod sursa (job #2940484) | Cod sursa (job #141777) | Cod sursa (job #2998855) | Cod sursa (job #3169518) | Cod sursa (job #1409922)
#include <fstream>
#include <deque>
#define MAXN 30005
#define INF 2000000000
using namespace std;
int n, l, u, c[MAXN], t[MAXN], v[MAXN], sp[MAXN];
int st = 0, dr = 100005, mid;
bool works(int x){
int i, smax = -INF;
deque<int> dq;
for(i = 1; i <= n; i++){
v[i] = c[i] - x * t[i];
sp[i] = sp[i - 1] + v[i];
}
for(i = l; i <= n; i++){
while(!dq.empty() && sp[i - l] <= sp[dq.back()])
dq.pop_back();
dq.push_back(i - l);
while(dq.front() < i - u) dq.pop_front();
if(sp[i] - sp[dq.front()] > smax) smax = sp[i] - sp[dq.front()];
}
return smax >= 0;
}
int main(){
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
int i;
scanf("%d %d %d", &n, &l, &u);
for(i = 1; i <= n; i++){
scanf("%d", &c[i]);
c[i] *= 100;
}
for(i = 1; i <= n; i++)
scanf("%d", &t[i]);
while(st < dr){
mid = (st + dr) >> 1;
if(works(mid)) st = mid + 1;
else dr = mid - 1;
}
while(!works(st)) st--;
printf("%d.%02d\n", st/100, st % 100);
return 0;
}