Cod sursa(job #597072)

Utilizator cosmyoPaunel Cosmin cosmyo Data 21 iunie 2011 02:26:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
using namespace std;
const int N = 100005;
int a[N], b[N], U, L, n;

int ok(double v) {
    int d[N], front = 1, back = 0, i;
    double s[N];
    s[0] = 0;
    for(i = 1; i <= n; ++i)
        s[i] = (double)s[i - 1] + ((double)a[i] -(double) b[i] * v);
  //  for(i = 1; i <= n; ++i)
    //    printf("%.2lf\n", s[i]);
    for(i = L  ; i <= n; ++i) {
        while(front <= back && s[d[back]] > s[i - L])
            --back;
        d[++back] = i - L;
            if(s[i] - s[d[front]] >= 0)
                return 1;

            if(i - L - d[front] +1 == U)
                ++front;
    }

    return 0;
}
int main(){
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    int i, j;
    scanf("%d%d%d", &n, &L, &U);
    for(i = 1;i <= n; ++i)
        scanf("%d", &a[i]);
    for(i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    const double eps = 0.0001;
    double rez = 0, step = 10000;
    for(; step > eps; step /= 2)
        if(ok(rez + step)){
      //      printf("%.2lf %.2lf\n", rez, step);
            rez += step;
        }
    printf("%.2lf\n", rez);
    return 0;
}