Pagini recente » Cod sursa (job #2008213) | Cod sursa (job #665922) | Cod sursa (job #2427172) | Cod sursa (job #2768988) | Cod sursa (job #983273)
Cod sursa(job #983273)
#include<stdio.h>
#include<math.h>
#include<deque>
#define NMAX 30000
#define eps 1.e-14
using namespace std;
struct DEQUE { int pos; double val; };
deque <DEQUE> dq;
int n,lo,hi,cost[NMAX+5],timp[NMAX+5];
double v[NMAX+5],sp[NMAX+5];
DEQUE make (int a, double b) {
DEQUE ret={a,b};
return ret;
}
int comp (double a, double b) {
if(fabs(a-b)<eps)
return 0;
if(a-b>=eps)
return 1;
return -1;
}
bool check (double val) {
int i;
double sum;
DEQUE aux;
while(!dq.empty())
dq.pop_back();
for(i=1;i<=n;i++) {
v[i]=cost[i]-(double)val*timp[i];
sp[i]=sp[i-1]+v[i];
}
sum=-2000000000;
dq.push_back(make(0,0));
for(i=0;i<=n-lo;i++) {
if(!dq.empty() && dq.front().pos < i+lo-hi)
dq.pop_front();
while(!dq.empty() && comp(dq.front().val,sp[i]) > 0)
dq.pop_back();
dq.push_back(make(i,sp[i]));
if(comp(sp[i+lo] - dq.front().val , sum) > 0)
sum=sp[i+lo]-dq.front().val;
}
return comp(sum,0) > 0;
}
double bs (double left, double right) {
double last,mid;
while(right-left>-eps) {
mid=(left+right)*0.5;
if(check(mid)) {
last=mid;
left=mid+0.01;
}
else
right=mid-0.01;
}
return last;
}
int main() {
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&n,&lo,&hi);
for(int i=1; i <= n ; i++)
scanf("%d",&cost[i]);
for(int i=1; i<= n; i++)
scanf("%d",&timp[i]);
printf("%.2lf\n",bs(0,30000000));
return 0;
}