Cod sursa(job #1737753)

Utilizator mariusn01Marius Nicoli mariusn01 Data 4 august 2016 18:19:05
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
// fixez x, in cautarea binara, ca fiind suma maxima. daca aleg o secventa, costul ei va fi
// (a1+a2+a3)/(b1+b2+b3). daca o secventa da costul y voi avea (a1+a2+a3)/(b1+b2+b3) = y
// echivalent cu a1+a2+a3 - b1*y-b2*y-b3*y = 0, asadar, pentru x fixat (si pus in loc de y),
// daca gasesc o astfel de relatie pozitiva inseamna ca suma secventei ce o da este >=x
// deci, cu x fixat voi cauta cea mai mare din astfel de expresii, si daca este pozitiva o sa maresc
// x, altfel il scad

#include <fstream>
#define DIM 300010
using namespace std;

int a[DIM], b[DIM], L, U, n, d[DIM], K;
double s[DIM], st, dr, mid;

int pozitiv(double mid) {
    s[0] = 0;
    for (int i=1;i<=n;i++)
        s[i] = s[i-1] + a[i] - b[i] * mid;
    int p, u;
    u = 0;
    p = 1;
    for (int i=1;i<=n;i++) {
        while (p <= u && s[i] >= s[ d[u] ])
            u--;
        d[++u] = i;
        if (i-d[p] == K)
            p++;

        if ( i >= L && i+L <= n)
            if (s[i+L] - s[ d[p] ] > 0)
                return 1;
    }
    return 0;
}

int main(){

    ifstream fin ("secv3.in");
    ofstream fout("secv3.out");
    fin>>n>>L>>U;
    K = U-L;
    for (int i=1;i<=n;i++)
        fin>>a[i];
    for (int i=1;i<=n;i++)
        fin>>b[i];

    st = 0;dr = 30000000;
    while (dr-st >= 0.001) {
        mid = (st + dr)/2;
        int rez = pozitiv(mid);
        if (rez)
            st = mid;
        else
            dr = mid;
    }

    fout<<st;

    return 0;
}