Nu exista pagina, dar poti sa o creezi ...

Cod sursa(job #2040746)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 16 octombrie 2017 15:06:33
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 30005
#define INF 0x3f3f3f

using namespace std;

int n, limMin, limMax, vElem[NMAX], vTimp[NMAX];
double vRez[NMAX];
deque <int> q;

void read()
{
    scanf("%d%d%d", &n, &limMin, &limMax);
    int nr;
    ///sume partiale
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &nr);
        vElem[i] = vElem[i-1] + nr;
    }
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &nr);
        vTimp[i] = vTimp[i-1] + nr;
    }
}

void resetDeque()
{
    while(!q.empty())
        q.pop_back();
}

int verifParte(double mijloc)
{
    for(int i=1; i<=n; ++i)
        vRez[i] = vElem[i] - (double)vTimp[i] * mijloc;

    resetDeque();

    for(int i=1; i<=n; ++i)
    {
        while(!q.empty() && vRez[i] <= vRez[q.back()])
            q.pop_back();

        q.push_back(i);

        if(i - q.front() > limMax - limMin)
            q.pop_front();

        if(vRez[i+limMin] - vRez[q.front()] > 0 && i+limMin <= n)
            return 1;
    }
    return 0;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    read();
    double st = 0, dr = INF;
    ///cautare binara
    while(dr - st >= 0.001)
    {
        double mij = (dr + st)/2;
        if(verifParte(mij))
            st = mij;
        else
            dr = mij;
    }
    printf("%.2lf", st);
    return 0;
}