Cod sursa(job #2643249)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 19 august 2020 12:13:37
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda prbd1 Marime 1.07 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)
{
    multiset<long long> s;

    for(int i=1;i<=n;i++)
    {
        if(i-low>=0)
            s.insert(100*a[i-low]-x*b[i-low]);

        if(i-up-1>=0)
        {
            auto it=s.find(100*a[i-up-1]-x*b[i-up-1]);
            s.erase(it);
        }

        if(s.empty())
            continue;

        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;
}