Pagini recente » Cod sursa (job #667664) | Cod sursa (job #48223) | Cod sursa (job #1488602) | Cod sursa (job #3124902) | Cod sursa (job #712094)
Cod sursa(job #712094)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n, l, u;
deque<int> dq;
double v[40000], p[40000], sum[40000];
void push_deque(int p) {
while (!dq.empty() && sum[dq.back()] >= sum[p])
dq.pop_back();
dq.push_back(p);
}
double get_deque(int poz) {
while (!dq.empty() && poz - dq.front() > u)
dq.pop_front();
return sum[dq.front()];
}
double sol(double a) {
int i;
double maxsum = -1;
dq.clear();
for (i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + (v[i] - p[i] * a);
if (i >= l)
push_deque(i - l);
if(i >= u)
maxsum = max(maxsum, sum[i] - get_deque(i));
}
return maxsum;
}
double binary_search () {
double i, step = 1024;
for (i = 0; step >= 0.001; step /= 2) {
if (sol(i + step) >= 0)
i += step;
}
return i;
}
int main()
{
int i;
fin >> n >> l >> u;
for (i = 1; i <= n; ++i)
fin >> v[i];
for (i = 1; i <= n; ++i)
fin >> p[i];
//fout.precision(2);
//fout.setf(ios::fixed, ios::floatfield);
fout << binary_search() << "\n";
fout.close();
return 0;
}