Pagini recente » Cod sursa (job #559591) | Cod sursa (job #3264026) | Cod sursa (job #537720) | Cod sursa (job #2092496) | Cod sursa (job #1904709)
#include <cstdio>
#include <deque>
using namespace std;
const int MAXN = 30000;
const double EPS = 0.001;
int c[MAXN + 1], t[MAXN + 1];
double v[MAXN + 1];
deque <int> deq;
int max_subarr(double x, int l, int u, int n) {
double maxim = 0.0;
for (int i = 1; i <= n; ++i)
v[i] = v[i - 1] + 1.0*c[i] - x*t[i];
deq.clear();
for (int i = l; i <= n; ++i) {
if (deq.front() == i - u - 1)
deq.pop_front();
while (deq.empty() == 0 && v[deq.back()] > v[i - l + 1])
deq.pop_back();
deq.push_back(i - l + 1);
if (v[i] - v[deq.front()] > 0)
return 1;
}
return 0;
}
int main()
{
FILE *fin, *fout;
double step, ans;
int n, l, u, i;
fin = fopen("secv3.in", "r");
fscanf(fin, "%d%d%d", &n, &l, &u);
for (i = 1; i <= n; ++i)
fscanf(fin, "%d", c + i);
for (i = 1; i <= n; ++i)
fscanf(fin, "%d", t + i);
fclose(fin);
for (ans=0.0, step = (1<<9); step > EPS; step /= 2.0)
if (max_subarr(ans + step, l, u, n))
ans += step;
fout = fopen("secv3.out", "w");
fprintf(fout, "%lf\n", ans);
fclose(fout);
return 0;
}