Cod sursa(job #1254808)

Utilizator diana97Diana Ghinea diana97 Data 3 noiembrie 2014 15:45:14
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

ifstream f ("secv3.in");
ofstream g ("secv3.out");

const int NMAX = 30000 + 1;

int n, l, u;
double cost[NMAX], timp[NMAX], s[NMAX];
int d[30010];

void citeste() {
    f >> n >> l >> u;
    for (int i = 1; i <= n; i++) f >> cost[i];
    for (int i = 1; i <= n; i++) f >> timp[i];
}

bool ok (double x) {
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + cost[i] - x * timp[i];
    deque <int> D;

    for (int i = l; i <= n; i++) {
        while (!D.empty() && s[i - l] <= s[D.back()]) D.pop_back();
        D.push_back(i - l);
        if (D.front() == i - u - 1) D.pop_front();
        if (s[i] - s[D.front()] > 0) return true;
    }
    return false;
}


void rezolva() {
    double st, dr, mid, sol, epsilon = 0.001;
    st=0; dr=2000000000;
    while (st<=dr) {
        mid=(st+dr)/2;
        if (ok(mid)){
            st=mid+0.001;
            sol=st;
        }else
            dr=mid-0.001;
    }

    g << fixed << setprecision(2) << sol << '\n';
}

int main() {
    citeste();
    rezolva();
    return 0;
}