Pagini recente » Cod sursa (job #773927) | Cod sursa (job #2284051) | Cod sursa (job #2840517) | Cod sursa (job #877624) | Cod sursa (job #1505707)
#include <fstream>
#include <deque>
using namespace std;
const int Nmax = 30000;
int c[Nmax+1],t[Nmax+1];
long long b[Nmax+1];
int N,L,U;
deque<int> D;
bool f(int x)
{
for (int i = 1; i <= N; i++)
b[i] = b[i-1] + c[i] - t[i] * x;
D.clear();
for (int i = L; i <= N; i++)
{
while (!D.empty() && i - D.front() > U)
D.pop_front();
while (!D.empty() && b[i-L] <= b[D.back()])
D.pop_back();
D.push_back(i-L);
if (b[i] - b[D.front()] >= 0)
return 1;
}
return 0;
}
int main()
{
ifstream fin("secv3.in");
ofstream fout("secv3.out");
fin >> N >> L >> U;
for (int i = 1; i <= N; i++)
fin >> c[i];
for (int i = 1; i <= N; i++)
fin >> t[i];
for (int i = 1; i <= N; i++)
c[i] *= 1000;
int i = 0;
int step = 1;
for (; step <= 1000000; step <<= 1);
for (; step; step >>= 1)
if (i+step <= 1000000 && f(i+step))
i += step;
fout << (double)i/1000 << "\n";
}