Cod sursa(job #3153902)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 1 octombrie 2023 23:17:09
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
long double sp1[30001],sp2[30001];
struct ura
{
    int ind;
    long double rez;
}dq[30001];
int main()
{
    int n,l,u,i,j1,j2,ok;
    long double st=0,dr=1e3,mij,poz,sum;
    cin>>n>>l>>u;
    for(i=1;i<=n;i++)
    {
        cin>>sp1[i];
        sp1[i]+=sp1[i-1];
    }
    for(i=1;i<=n;i++)
    {
        cin>>sp2[i];
        sp2[i]+=sp2[i-1];
    }
    while(st<=dr)
    {
        mij=(st+dr)/2;
        ok=0;
        dq[1].ind=0;
        dq[1].rez=0;
        for(j1=1,j2=1,i=l;i<=n&&ok==0;i++)
        {
            if(dq[j1].ind<i-u)
                j1++;
            sum=sp1[i-l]-sp2[i-l]*mij;
            while(j2>=j1&&dq[j2].rez>=sum)
                j2--;
            j2++;
            dq[j2].rez=sum;
            dq[j2].ind=i-l;
            if(sp1[i]-sp2[i]*mij-dq[j1].rez>=0)
                ok=1;
        }
        if(ok==0)
            dr=mij-0.001;
        else
        {
            poz=mij;
            st=mij+0.001;
        }
    }
    cout<<poz;
    return 0;
}