Cod sursa(job #712093)

Utilizator deneoAdrian Craciun deneo Data 13 martie 2012 01:15:50
Problema Secventa 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

int n, l, u;
deque<int> dq;
double v[40000], p[40000], sum[40000];

void push_deque(int p) {
    while (!dq.empty() && sum[dq.back()] >= sum[p])
        dq.pop_back();
    dq.push_back(p);
}

double get_deque(int poz) {
    while (!dq.empty() && poz - dq.front() > u)
        dq.pop_front();
    return sum[dq.front()];
}

double sol(double a) {
    int i;
    double maxsum = -1;
    dq.clear();
    for (i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + (v[i] - p[i] * a);
        if (i >= l)
            push_deque(i - l);
        if(i >= u)
            maxsum = max(maxsum, sum[i] - get_deque(i));
    }
    return maxsum;
}

double binary_search () {
    double i, step = 1024;
    for (i = 0; step >= 0.001; step /= 2) {
        if (sol(i + step) >= 0)
            i += step;
    }
    return i;
}

int main()
{
    int i;
    fin >> n >> l >> u;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    for (i = 1; i <= n; ++i)
        fin >> p[i];
    fout.precision(2);
    fout.setf(ios::fixed, ios::floatfield);
    fout << binary_search() << "\n";
    fout.close();
    return 0;
}