Pagini recente » Cod sursa (job #1984451) | Borderou de evaluare (job #1572118) | Cod sursa (job #3182417) | Cod sursa (job #885210) | Cod sursa (job #761047)
Cod sursa(job #761047)
#include <cstdio>
#include <deque>
#define NMax 30005
#define Infinity 1000000
using namespace std;
int N, L, U, C[NMax], T[NMax];
double X[NMax], Solution;
deque <int> D;
void Read ()
{
freopen ("secv3.in", "r", stdin);
scanf ("%d %d %d", &N, &L, &U);
for (int i=1; i<=N; ++i)
{
scanf ("%d", &C[i]);
}
for (int i=1; i<=N; ++i)
{
scanf ("%d", &T[i]);
}
}
void Print ()
{
freopen ("secv3.out", "w", stdout);
printf ("%.2lf\n", Solution);
}
bool Solve (double S)
{
for (int i=1; i<=N; ++i)
{
X[i]=X[i-1]+C[i]-T[i]*S;
}
for (int i=L; i<=N; ++i)
{
while (!D.empty () and X[D.back ()]>=X[i-L+1])
{
D.pop_back ();
}
D.push_back (i-L);
while (D.front ()<i-U)
{
D.pop_front ();
}
if (X[i]-X[D.front ()]>=0)
{
D.clear ();
return true;
}
}
D.clear ();
return false;
}
int main()
{
Read ();
double Left=0, Right=Infinity;
while (Right-Left>0.0001)
{
double Mid=(Left+Right)/2;
if (Solve (Mid))
{
Left=Mid+0.0001;
Solution=Mid;
}
else
{
Right=Mid-0.0001;
}
}
Print ();
return 0;
}