Cod sursa(job #2351381)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 22 februarie 2019 12:34:09
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <iomanip>

using namespace std;

ifstream cin("secv3.in");
ofstream cout("secv3.out");

const int N=30000+7;

int n;
int l;
int r;

int a[N];
int b[N];

double ugar[N];

double kek[N];

struct DEQ
{
        int d[N];
        int st;
        int dr;
        void clr()
        {
                st=1;
                dr=0;
        }
        void add(int id)
        {
                while(st<=dr && ugar[d[dr]]<=ugar[id])
                {
                        dr--;
                }
                d[++dr]=id;
        }
        void del(int id)
        {
                if(st<=dr && d[st]==id)
                {
                        st++;
                }
        }
        double gt()
        {
                return ugar[d[st]];
        }
};

DEQ d;

bool ok(double x)
{
        d.clr();
        for(int i=1;i<=n;i++)
        {
                ugar[i]=(double)a[i]-(double)b[i]*x;
                ugar[i]+=ugar[i-1];
        }
        int tot=r-l+1;
        for(int i=1;i<=tot;i++)
        {
                d.add(i);
        }
        for(int i=1;i<=n;i++)
        {
                kek[i]=d.gt();
                d.del(i);
                if(i+tot<=n)
                {
                        d.add(i+tot);
                }
        }
        for(int i=1;i+l-1<=n;i++)
        {
                double vl=kek[i+l-1];
                if(vl-ugar[i-1]>=0)
                {
                        return 1;
                }
        }
        return 0;
}

int main()
{
        cin>>n;
        cin>>l>>r;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
                cin>>b[i];
        }
        double lo=0;
        double hi=1000*1000;
        for(int i=1;i<=100;i++)
        {
                double mid=(lo+hi)*0.5;
                if(ok(mid))
                {
                        lo=mid;
                }
                else
                {
                        hi=mid;
                }
        }
        cout<<fixed<<setprecision(2)<<lo<<"\n";
        return 0;
}