Cod sursa(job #658553)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 8 ianuarie 2012 23:49:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <iomanip>
#include <deque>
#define MAXN 30010
using namespace std;

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

int n,c[MAXN],t[MAXN],i,l,u;
double r[MAXN],sol;
deque<int> Mind;
void push(int i) {
    while (!Mind.empty() && r[i]<=r[Mind.back()]) Mind.pop_back();
    Mind.push_back(i);
}
int query(int i) {
    i=max(i-u,0);
    while (!Mind.empty() && Mind.front()<i) Mind.pop_front();
    return Mind.front();
}
bool possible (double v) {
    Mind.clear();
    for (i=1;i<=n;i++)
        r[i]=r[i-1]+c[i]-t[i]*v;
    for (i=l;i<=n;i++) {
        push(i-l);
        int q=query(i);
        if (r[i]>=r[q]) return true;
    }
    return false;
}
void bin_search() {
    double m,p=0,u=100000;
    while (u-p>0.001) {
        m=p+(u-p)/2;
        if (possible(m)) {
            sol=m;
            p=m+0.0001;
        }
        else u=m-0.0001;
    }
}

int main () {
    f >> n >> l >> u;
    for (i=1;i<=n;i++) f >> c[i];
    for (i=1;i<=n;i++) f >> t[i];
    bin_search();
    g << fixed;
    g << setprecision(2) << sol << '\n';
    f.close();g.close();
    return 0;
}