Cod sursa(job #2209003)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 1 iunie 2018 14:44:09
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
FILE *in, *out;

const int NMAX = 30005;
const double eps = 0.001;
int c[NMAX], t[NMAX], n, l, u;
double s[NMAX];

bool ok(double val) {
    deque<int> d;
    d.push_front(1);
    for(int i = 1;i <= n;i ++)
        s[i] = 1.0 * c[i] -  val * 1.0 * t[i];
    for(int i = l;i <= n; 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, "%d", &c[i]);
        c[i] += c[i-1];
    }
    for(int i = 1; i <= n; i ++) {
        fscanf(in, "%d", &t[i]);
        t[i] += t[i-1];
    }
    double ans = 0.0;
    for(double step = (1 << 9); step > eps; step /= 2.0)
        if(ok((ans + step)))
            ans += step;
    fprintf(out,"%lf", ans);
    return 0;
}