Mai intai trebuie sa te autentifici.
Cod sursa(job #604828)
Utilizator | Data | 25 iulie 2011 15:52:57 | |
---|---|---|---|
Problema | Secventa 3 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.08 kb |
#include <cstdio>
const int N = 30010;
int n, l, u, a[N], b[N], dq[N];
int st, dr;
double s[N];
const double eps = 0.01;
void read() {
scanf("%d%d%d", &n, &l, &u);
for (int i = 1; i <= n; ++ i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++ i)
scanf("%d", &b[i]);
}
void elimst(int poz) {
if (st <= dr && dq[st] == poz - u)
++ st;
}
void elimdr(int poz) {
while (dr >= st && s[poz - l] < s[dq[dr]])
-- dr;
}
bool verif(double val) {
st = 1, dr = 0;
for (int i = 1; i <= n; ++ i)
s[i] = (double)s[i - 1] + (double)a[i] - val * (double)b[i];
for (int i = l; i <= n; ++ i) {
elimst(i);
elimdr(i);
dq[++ dr] = i - l;
if (s[i] - s[dq[st]] > - eps)
return 1;
}
return 0;
}
double cautb() {
double mij, sol = 0, s = 0, d = (1 << 30);
while (s + eps < d) {
mij = (s + d) * 0.5;
if (verif(mij)) {
sol = mij;
s = mij;
} else
d = mij;
}
return sol;
}
int main() {
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
read();
printf("%.2lf", cautb());
return 0;
}