Pagini recente » Cod sursa (job #64872) | Cod sursa (job #17989) | Cod sursa (job #45470) | Cod sursa (job #21780) | Cod sursa (job #22267)
Cod sursa(job #22267)
#include <stdio.h>
#include <deque>
using namespace std;
#define infile "secv3.in"
#define outfile "secv3.out"
#define NMAX 30005
#define INF 1000000000000000.1
FILE *fin,*fout;
int N,L,U;
int c[NMAX],t[NMAX];
double suma[NMAX];
deque <int> D;
void citire()
{
int i;
fin=fopen(infile,"r");
fscanf(fin,"%d %d %d",&N,&L,&U);
for(i=1;i<=N;i++)
fscanf(fin,"%d",&c[i]);
for(i=1;i<=N;i++)
fscanf(fin,"%d",&t[i]);
fclose(fin);
}
void adauga_deque(int x)
{
while(!D.empty() && suma[D.back()]>=suma[x])
D.pop_back();
D.push_back(x);
}
void elimina_deque(int x)
{
if(!D.empty() && D.front()==x)
D.pop_front();
}
inline double minim_deque()
{
return suma[D.front()];
}
double sumamax(double X)
{
int i;
double sol=-INF;
suma[0]=0.;
for(i=1;i<=N;i++)
suma[i]=suma[i-1]+c[i]-X*t[i];
D.clear();
for(i=L;i<=N;i++)
{
elimina_deque(i-U-1);
adauga_deque(i-L);
if(sol<suma[i]-minim_deque())
sol=suma[i]-minim_deque();
}
return sol;
}
double solve(double li, double ls)
{
double mij=(li+ls)/2.;
if(ls-li<0.001)
return mij;
double s=sumamax(mij);
if(s<0)
return solve(li,mij);
else
return solve(mij,ls);
}
int main()
{
citire();
fout=fopen(outfile,"w");
fprintf(fout,"%lf\n",solve(0,1000));
fclose(fout);
return 0;
}