Pagini recente » Istoria paginii runda/verificareoni/clasament | Cod sursa (job #1231311) | Cod sursa (job #1949513) | Cod sursa (job #1771559) | Cod sursa (job #999474)
Cod sursa(job #999474)
#include <fstream>
#include <deque>
#define In "secv3.in"
#define Out "secv3.out"
#define Nmax 30005
#define EPS 1e-2
#define Inf 0x3f3f3f3f
using namespace std;
int a[Nmax], b[Nmax];
int n,l,u;
double sum[Nmax],sol=Inf;
inline void Read()
{
ifstream f(In);
f>>n>>l>>u;
int i;
for(i = 1;i <=n; ++i)
f>>a[i];
for(i = 1 ;i<=n;++i)
f>>b[i];
f.close();
}
inline bool Verif(const double x)
{
deque< int >D;
int i;
double Best = -Inf;
for(i = 1;i <= n; ++i)
sum[i] = sum[i-1] + a[i]-(b[i]*x);
D.push_back(0);
for(i = u;i <= n; ++i)
{
while(!D.empty() && sum[D.back()]>=sum[i-l])
D.pop_back();
D.push_back(i-l);
while(D.front() < i-u)
D.pop_front();
Best = max(Best,sum[i]-sum[D.front()]);
}
return (Best>=0);
}
inline void Solve()
{
double middle,Left,Right;
while(Right-Left>EPS)
{
if(Verif(middle))
{
sol = middle;
Left = middle+1;
}
else
Right = middle-1;
}
}
inline void Write()
{
freopen(Out,"w",stdout);
printf("%.2lf\n",sol);
}
int main()
{
Read();
Solve();
Write();
return 0;
}