Pagini recente » Cod sursa (job #2747674) | Cod sursa (job #735428) | Cod sursa (job #2256899) | Cod sursa (job #1761122) | Cod sursa (job #1452278)
#include <fstream>
#include <iostream>
#include <deque>
#include <cstring>
#include <iomanip>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
const int NSIZE = 30000 + 10;
deque < int > inDeque;
int d[NSIZE] , x[NSIZE] , y[NSIZE];
int bsl , bsr , k , f , le , ri , N , i;
bool check(int k)
{
memset(d,0,sizeof(d));
while (inDeque.size()) inDeque.pop_back();
for (i = 1 ; i <= N ; ++i)
d[i] = d[i - 1] + x[i] - y[i] * k;
for (i = le ; i <= N ; ++i)
{
while (inDeque.size() && d[i - le] <= d[inDeque.back()])
inDeque.pop_back();
inDeque.push_back(i - le);
while (inDeque.front() < i - ri)
inDeque.pop_front();
if (d[i] - d[inDeque.front()] >= 0) return true;
}
return false;
}
int main()
{
fin >> N >> le >> ri;
for (i = 1 ; i <= N ; ++i)
{
fin >> x[i];
x[i] *= 100;
}
for (i = 1 ; i <= N ; ++i)
fin >> y[i];
bsl = 0 , bsr = 100000;
while (bsl <= bsr)
{
int k = (bsl + bsr) >> 1;
if (check(k))
{
bsl = k + 1;
f = k;
} else bsr = k - 1;
}
fout << setprecision(3) << fixed << 1.0 * f / 100 << '\n';
return 0;
}