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