Pagini recente » Cod sursa (job #237804) | Cod sursa (job #972602) | Cod sursa (job #926167) | Cod sursa (job #2732007) | Cod sursa (job #878716)
Cod sursa(job #878716)
#include <iostream>
#include <fstream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define MAX 32020
int cost[MAX];
int timp[MAX];
double C[MAX];
double T[MAX];
int n, l, u;
ifstream in("secv3.in");
ofstream out("secv3.out");
int st, ed;
int stack[MAX];
double rez;
double cst(int i)
{
return C[i]/rez-T[i];
}
void insert(int x)
{
if(ed = -1)
{
stack[0]=x;
st=ed=0;
return;
}
ed++;
stack[ed]=x;
while(ed>0 && ed!=st)
if(cst(stack[ed]) < cst(stack[ed-1]))
{
stack[ed-1]=stack[ed];
ed--;
}
}
int top()
{
return stack[ed];
}
int bottom()
{
if(ed==-1)
return -1;
return stack[st];
}
void discardbottom()
{
st++;
}
void clear()
{
ed = -1;
}
int size()
{
return ed-st+1;
}
int main() {
in>>n>>l>>u;
int i;
double arez=1.0/1000, brez=1000.0;
for(i=1;i<=n;i++)
in>>cost[i];
for(i=1;i<=n;i++)
in>>timp[i];
T[0]=timp[0];
for(i=1;i<=n;i++)
T[i]=T[i-1]+timp[i];
for(i=1;i<=n;i++)
C[i]=C[i-1]+cost[i];
rez=(brez+arez)/2;
while((brez-arez)>0.01)
{
rez = (brez+arez)/2;
clear();
insert(0);
int i=1;
int j;
for(j=l;j<=n;j++)
{
int k = bottom();
if(cst(j) >= cst(k))
{ // it is viable
arez = rez;
break;
}
insert(i);
i++;
if(size()>u-l)
discardbottom();
}
if(j>n)
brez = rez;
}
rez =(brez+arez)/2.0;
out<<rez<<"\n";
return 0;
}