Cod sursa(job #1251313)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 29 octombrie 2014 11:40:46
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>

using namespace std;

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

double st,dr,mid,t[30010],c[30010],s[30010],sol;

int d[30010],n,l,u;

bool verif (double T) {
    int st,dr;
    for (int i=1;i<=n;i++)
        s[i]=s[i-1]+c[i]-T*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(d[st]==i-u-1)
            st++;
        if(s[i]-s[d[st]]>0)
            return 1;
    }
    return 0;
}

int main () {

    fin>>n>>l>>u;
    for (int i=1;i<=n;i++)
        fin>>c[i];
    for (int i=1;i<=n;i++)
        fin>>t[i];
    st=0; dr=2000000000;
    while (st<=dr) {
        mid=(st+dr)/2;
        if (verif(mid))
        {
            st=mid+0.001;
            sol=st;
        }
        else
            dr=mid-0.001;
    }
    fout<<sol<<"\n";
    return 0;
}