Cod sursa(job #2643223)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 19 august 2020 11:20:44
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda prbd1 Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("secv3.in");
ofstream fout ("secv3.out");
int n,i,low,up;
long long st,dr,mij,last;
long long a[30005];
long long b[30005];
bool ok(long long x)
{
    int r=-1, l=0;
    multiset<long long> s;

    for(int i=1;i<=n;i++)
    {
        while(r<i-low)
        {
            r++;
            s.insert(100*a[r]-x*b[r]);
        }
        while(l<i-up)
        {
            auto it=s.find(100*a[l]-x*b[l]);
            s.erase(it);
            l++;
        }

        if(100*a[i]-x*b[i] >= *s.begin())
            return true;
    }

    return false;
}
int main()
{
    fin>>n>>low>>up;
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        a[i]+=a[i-1];
    }
    for(i=1;i<=n;i++)
    {
        fin>>b[i];
        b[i]+=b[i-1];
    }

    st=0;
    dr=3*1e9;

    while(st<=dr)
    {
        mij=(st+dr)/2;

        if(ok(mij))
        {
            last=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }

    fout<<last/100<<'.'<<last%100;
    return 0;
}