Pagini recente » Cod sursa (job #194094) | Cod sursa (job #797925) | Cod sursa (job #1502557) | Cod sursa (job #1506079) | Cod sursa (job #2208975)
#include <bits/stdc++.h>
using namespace std;
FILE *in, *out;
const int NMAX = 30005;
long long c[NMAX], t[NMAX], s[NMAX];
int n, l, u;
bool ok(int val) {
deque<int> d;
d.push_front(1);
for(int i = l;i <= n; i ++) {
s[i] = c[i] - 1LL * val * t[i];
if(!d.empty() && d.front() == i - u - 1)
d.pop_front();
while(!d.empty() && s[d.back()] > s[i - l + 1])
d.pop_back();
d.push_back(i - l + 1);
if(s[i] - s[d.front()] > 0)
return 1;
}
return 0;
}
int main() {
in = fopen("secv3.in", "r");
out = fopen("secv3.out", "w");
fscanf(in, "%d %d %d", &n, &l, &u);
for(int i = 1; i <= n; i ++) {
fscanf(in, "%lld", &c[i]);
c[i] += c[i-1];
}
for(int i = 1; i <= n; i ++)
c[i] *= 1000;
for(int i = 1; i <= n; i ++) {
fscanf(in, "%lld", &t[i]);
t[i] += t[i-1];
}
int ans = 0;
for(int step = 1 << 19; step > 0; step >>= 1)
if(ok((ans + step)))
ans += step;
fprintf(out,"%d.%03d", ans / 1000, ans % 1000);
return 0;
}