Pagini recente » Cod sursa (job #1327887) | Cod sursa (job #1000520) | Cod sursa (job #1088809) | Cod sursa (job #1348073) | Cod sursa (job #999489)
Cod sursa(job #999489)
#include <iostream>
#include <fstream>
#include <deque>
#define NMax 30010
using namespace std;
int n, l, u;
int cost[NMax], timp[NMax];
double sol;
inline void Read()
{
ifstream f ("secv3.in");
f>>n>>l>>u;
int i;
for (i=1; i<=n; ++i)
f>>cost[i];
for (i=1; i<=n; ++i)
f>>timp[i];
f.close();
}
inline bool Verif (double x)
{
double aux[NMax], sum[NMax], solaux = -10000.0;
int st, dr;
deque <int> dq;
sum[0] = 0.0;
for (int i=1; i<=n; ++i)
aux[i] = 1.0*cost[i] - x*timp[i],
sum[i] = sum[i-1] + aux[i];
st = 0, dr = l;
dq.push_back(st);
for (; dr<=n; ++dr)
{
while (!dq.empty() && dr-dq.front() > u)
dq.pop_front();
while (!dq.empty() && sum[dr-l] <= dq.back())
dq.pop_back();
dq.push_back(dr-l);
solaux = max(solaux, sum[dr] - sum[dq.front()]);
}
if (solaux >= 0.0)
return true;
return false;
}
inline void Solve()
{
double st, dr, mij;
st = 0.0, dr = 1000.0;
while (dr-st > 0.001)
{
mij = (st+dr)/2.0;
if (Verif(mij))
{
sol = mij;
st = mij + 0.001;
}
else
dr = mij - 0.001;
}
}
inline void Write()
{
freopen ("secv3.out", "w", stdout);
printf("%.2lf\n", sol);
}
int main()
{
Read();
Solve();
Write();
return 0;
}