Cod sursa(job #777269)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 11 august 2012 18:31:15
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <deque>
#include <iomanip>

#define MAX 30005
#define ERR 0.01

using namespace std;

int cost[MAX], timp[MAX], n, l, u;
double c[MAX];

bool solution(double med)
{
    deque<int> dq;
    c[0] = 0;
    for(int i = 1; i <= n; i++)
        c[i] = c[i - 1] + (double)cost[i] - med * timp[i];
    dq.push_front(0);
    for(int i = l; i <= n; i++)
    {
        while(!dq.empty() && c[i - l] < c[dq.back()])
            dq.pop_back();
        dq.push_back(i - l);
        if(dq.front() == i - u - 1) dq.pop_front();
        if(c[i] - c[dq.front()] >= 0) return true;
    }
    return false;
}

double solve()
{
    double l = 0, r = 1000, m, sol;
    while(r > l)
    {
        m = (r + l) / 2;
        if(solution(m))
        {
            l = m + ERR;
            sol = m;
        }
        else
            r = m - ERR;
    }
    return sol;
}

int main()
{
    ifstream in("secv3.in"); in>>n>>l>>u;
    for(int i = 1; i <= n; i++) in>>cost[i];
    for(int i = 1; i <= n; i++) in>>timp[i];
    ofstream out("secv3.out"); out<<fixed<<setprecision(2)<<solve(); out.close();
    return 0;
}