Cod sursa(job #1122720)

Utilizator misinozzz zzz misino Data 25 februarie 2014 20:05:50
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#include<deque>
#define N 30100
using namespace std;
ifstream f("secv3.in");
ofstream g("secv3.out");
int n,i,l,u,c[N],t[N];
double mij,li,ls,sol;
deque<int>d;
inline bool verif(double timp)
{
    int i,sol;
    double s[N];
    for(i=1;i<=n;++i)
    s[i]=s[i-1]+c[i]-t[i]*timp;
    d.clear();
    if(s[l]>0)
    return 1;
    for(i=l;i<=n;++i)
    {
        while(!d.empty()&&d.front()<i-u)
        d.pop_front();
        while(!d.empty()&&s[d.back()]>=s[i-l])
        d.pop_back();
        d.push_back(i-l);
        if(s[i]-s[d.front()]>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];
    li=0;
    ls=1<<30;
    while(li<=ls)
    {
        mij=(li+ls)/2;
        if(verif(mij))
        li=mij+0.001,sol=mij;
        else
        ls=mij-0.001;
    }
    g<<sol<<'\n';
    return 0;
}