Pagini recente » Cod sursa (job #2210889) | Cod sursa (job #2940681) | Cod sursa (job #2322957) | Cod sursa (job #2796393) | Cod sursa (job #214299)
Cod sursa(job #214299)
#include<stdio.h>
#define NMAX 30024
double S[NMAX],T[NMAX];
int DEQ[NMAX];
//daca nici asa nu merge tre sa ma las de idei geniale si sa ma apuc
//de debug la sursa de O(N*logN)
int i1,s1;
double a1,a2;
inline double max(const double a,const double b){ return a>b?a:b; }
void read_init(const int N)
{
int i;
for(i=1; i<=N; ++i)
{
scanf("%lf",&S[i]);
S[i]+=S[i-1];
}
for(i=1; i<=N; ++i)
{
scanf("%lf",&T[i]);
T[i]+=T[i-1];
}
}
inline bool comp(const int p1,const double V2)
{
const double V1=(S[p1]-a1)/(T[p1]-a2);
if( V1<=V2 )return 0;
return 1;
}
void add(const double val,const int poz,const int K)
{
if( !i1 ){
DEQ[i1=s1=1]=poz;return;}
if( !comp(DEQ[s1],val) || DEQ[ s1 ]<K )
{
if( !comp(DEQ[i1],val) ){
DEQ[i1=s1=1]=poz;return;}
while( !comp(DEQ[s1],val) || DEQ[s1]<K )
--s1;
DEQ[++s1]=poz;return;
}
DEQ[++s1]=poz;
}
void erase(const int poz)
{
while( DEQ[i1]<poz )++i1;
}
inline double calc(const int poz)
{
return (S[poz]-a1)/(T[poz]-a2);
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
int N,L,U;
scanf("%d%d%d",&N,&L,&U);
read_init(N);
double solfin,val;
int i,j;
for(i=L; i<=U; ++i)
{
val=S[i]/T[i];a1=a2=0;
add(val,i,i-U+1);
solfin=max(solfin,val);
}
for(i; i<=N; ++i)
{
erase(i-U+1);
a1=S[i-U];a2=T[i-U];
val=(S[i]-a1)/(T[i]-a2);
add(val,i,i-U+1);
solfin=max(solfin,calc(DEQ[i1]));
}
for(j=N-U+1,i=N; i-j>=L; ++j)
{
erase(j+1);
a1=S[j];a2=T[j];
val=(S[N]-a1)/(T[N]-a2);
solfin=max(solfin,calc(DEQ[i1]));
}
printf("%0.2lf\n",solfin);
return 0;
}