Pagini recente » Cod sursa (job #2586502) | Cod sursa (job #1858439) | Cod sursa (job #106767) | Cod sursa (job #863805) | Cod sursa (job #2924693)
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=30005;
int N, L, U, c[NMAX], t[NMAX];
double aux[NMAX]/*=Suma pt j=0,i din c[j]-T*t[j]*/;
int dq[NMAX], st, end;
bool is_doable(double T)
{
int i;
aux[0]=0;
for(i=0;i<N;++i)
aux[i+1]=aux[i]+c[i]-t[i]*T;
st=0, end=1;
dq[0]=0;
/*
sc
-- >= T
st
sc-st*T>=0
aux[i]-aux[j]>=0
*/
if(aux[L]>=0)
return 1;
for(i=L;i<N;++i)
{
while(dq[st]<=i-U && st<end)
++st;
while(st<end && aux[dq[end-1]]>=aux[i-L+1])
--end;
dq[end++]=i-L+1;
if(aux[i+1]-aux[dq[st]]>=0)
return 1;
}
return 0;
}
int main()
{
FILE* f=fopen("secv3.in", "r"), *g=fopen("secv3.out", "w");
int i;
double l=0.001, r=1000, m;
fscanf(f, "%d%d%d", &N, &L, &U);
for(i=0;i<N;++i)
fscanf(f, "%d", c+i);
for(i=0;i<N;++i)
fscanf(f, "%d", t+i);
fclose(f);
for(i=0;i<20;++i)
{
m=(l+r)*0.5;
if(is_doable(m))
l=m;
else
r=m;
}
i=l*100;
fprintf(g, "%d.%02d", i/100, i%100);
fclose(g);
return 0;
}