Cod sursa(job #1393317)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 19 martie 2015 11:55:07
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("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()
{
    fin>>n>>L>>U;
    for(i=1;i<=n;i++)
        fin>>c[i];
    for(i=1;i<=n;i++)
        fin>>t[i];
    st=0;dr=2000000000;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(secv(mid))
        {
            sol=mid;
            st=mid+0.001;
        }
        else
            dr=mid-0.001;
    }
    fout<<sol;
    return 0;
}