Cod sursa(job #1006045)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 6 octombrie 2013 10:42:15
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iomanip>
#include <deque>

#define maxn 30001

using namespace std;


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

deque<int> D;

double v[maxn],t[maxn];
int n,l,u;
double hi,lo,mid;

bool check_sum (double val)
{
    D.clear();

    double s[maxn];
    s[0]=0;

    for (int i=1; i<=n; ++i)
    {
        s[i] = s[i-1] + v[i] - val*t[i];
    }

    D.push_back (0);
    double maxv = s[l],current = s[l];

    for (int i=l+1; i<=n; ++i)
    {
        while (!D.empty() && s[i-l] <= s[D.front()]) D.pop_back();
        D.push_back (i-l);

        if (D.front() < i-u) D.pop_front();

         current = s[i] - s[D.front()];

         if (current > maxv) maxv = current;
    }

    if (current > 0) return 1;
    return 0;
}

int main()
{
    fin>>n>>l>>u;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i];
        hi += v[i];
    }

    for (int i=1; i<=n; ++i)
    {
        fin>>t[i];
    }

    lo = -1;
    hi+=1;

    while (hi - lo > 0.001)
    {
        mid = (lo+hi)/2;
        if (check_sum(mid)) lo =mid;
        else hi = mid;
    }

    fout<<fixed<<setprecision(2)<<hi;
}