Pagini recente » Cod sursa (job #2711843) | Cod sursa (job #1552994) | Cod sursa (job #846051) | Cod sursa (job #1423631) | Cod sursa (job #2099555)
#include <cstdio>
const int MAXN = 3e4;
const double EPS = 1e-3;
int c[MAXN], t[MAXN], dq[MAXN + 1];
double s[MAXN + 1];
bool check(double x, int l, int u, int n) {
int b, e;
s[0] = 0.0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + 1.0 * c[i - 1] - x * t[i - 1];
}
b = e = 0;
for (int i = l; i <= n; ++i) {
if (dq[b] + u == i - 1) {
++b;
}
while (b < e && s[dq[e - 1]] > s[i - l + 1]) {
--e;
}
dq[e++] = i - l + 1;
if (s[i] - s[dq[b]] > 0) {
return 1;
}
}
return 0;
}
int main() {
int n, l, u;
double x, i;
FILE *f = fopen("secv3.in", "r");
fscanf(f, "%d%d%d", &n, &l, &u);
for (int i = 0; i < n; ++i) {
fscanf(f, "%d", &c[i]);
}
for (int i = 0; i < n; ++i) {
fscanf(f, "%d", &t[i]);
}
fclose(f);
i = (1 << 9);
for (x = 0.0; i > EPS; i /= 2.0) {
if (check(i + x, l, u, n)) {
x += i;
}
}
f = fopen("secv3.out", "w");
fprintf(f, "%.2lf\n", x);
fclose(f);
return 0;
}