Pagini recente » Cod sursa (job #761464) | Cod sursa (job #2053521) | Cod sursa (job #801568) | Cod sursa (job #1020564) | Cod sursa (job #930129)
Cod sursa(job #930129)
#include <cstdio>
#include <cmath>
#define INF "secv3.in"
#define OUF "secv3.out"
#define NMAX 30002
#define EPS 1e-4
using namespace std;
long long n,l,u,c[NMAX],t[NMAX];
long long sumk(long long k)
{
long long i,p,q,ok,dq[NMAX],p1,p2;
long long v[NMAX],max;
v[0]=0;
for(i=1;i<=n;++i) v[i]=(c[i]-k*t[i])+v[i-1];//printf("%d ",v[i]);}
//printf("\n");
max=-1000000;ok=0;
if(v[l]>max) max=v[l];
if(max>0) ok=1;
p=1;q=0; i=l+1;
while(i<=n)
{
dq[++q]=i-l;
if(dq[p]<i-u) ++p;
while(q>p&&v[i-l]<v[dq[q-1]])
{
--q;
dq[q]=i-l;
}
if(v[i]-v[dq[p]]>max)
{
max=v[i]-v[dq[p]];
if(max>0) ok=1;
p1=i;p2=dq[p]+1;
}
++i;
}
//printf("%d %d \n",p1,p2);
return ok;
}
int main()
{
long long i,max,st,dr,mij,c1,c2;
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
fscanf(in,"%lld%lld%lld",&n,&l,&u);
c[0]=t[0]=0;
for(i=1;i<=n;++i) {fscanf(in,"%lld",c+i);c[i]*=100;}
for(i=1;i<=n;++i) {fscanf(in,"%lld",t+i);t[i]*=1;}
st=1;dr=100000;max=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(sumk(mij))
{
max=mij;
st=mij+1;
}
else dr=mij-1;
}
// printf("%d\n",max);
c1=(max/10)%10;c2=max%10;
fprintf(out,"%lld.%lld%lld\n",max/100,c1,c2);
// printf("%d",max);
// scanf("%d",&i);
fclose(in);fclose(out);
return 0;
}