Cod sursa(job #1609402)

Utilizator CatlinvCatalin Sbera Catlinv Data 22 februarie 2016 19:46:35
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

ifstream f("secv3.in");
ofstream g("secv3.out");

int i, n, L, U,D[30100], c[30100], t[30100];
double s[30100], st, dr, mid, sol;

int secv(double S)
{
    int st, dr;
    for (int i = 1; i <= n; i++)
        s[i] = s[i-1]+ c[i] - S*t[i];
    st = 1;
    dr = 0;
    for(int i = L; i <= n; i ++)
    {
        while (st <= dr && s[i - L] <= s[D[dr]])
            dr--;
        D[++dr] = i - L;
        if (i - U - 1 == D[st] )
            st++;
        if (s[i] - s[D[st]] > 0)
            return 1;
    }
    return 0;
}
int main()
{
    f>>n>>L>>U;
    for (i = 1; i <= n; i++)
        f>>c[i];
    for (i = 1; i <= n; i++)
        f>>t[i];
    st = 0;
    dr = 2000000000;
    while (st <= dr)
    {
        mid = (st + dr) / 2;
        if (secv(mid))
        {
            sol = st;
            st = mid + 0.001;
        }
        else
            dr = mid - 0.001;
    }
    g << sol;
    return 0;
}