Cod sursa(job #2643304)

Utilizator adiaioanaAdia R. adiaioana Data 19 august 2020 14:24:46
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>
#include <iomanip>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");
int l,u,N, c[30100], t[30100], ps[30100];
deque <int> deq;
bool work(int val);
int main()
{
    cin>>N>>l>>u;
    for(int i=1; i<=N; ++i)
        cin>>c[i], c[i]*=100;

    for(int i=1; i<=N; ++i)
        cin>>t[i];

    int ans=-100, st=1, dr=3000000, mij=0;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(work(mij))
        {
            ans=mij;
            st=mij+1;
        }
        else dr=mij-1;
    }
    cout<<ans/100<<'.';
    if(ans%100<10)
        cout<<0;
    cout<<ans%100<<'\n';
    return 0;
}

bool work(int val)
{
    for(int i=1; i<=N; ++i)
        ps[i]=ps[i-1]+(c[i]-val*t[i]);
    deq.clear();
    deq.push_front(0);
    int sol=0;
    for(int i=l; i<=N; ++i)
    {
        while(!deq.empty() && deq.front()<i-u)
            deq.pop_front();
        while(!deq.empty() && ps[deq.back()]>=ps[i-l])
            deq.pop_back();
        deq.push_back(i-l);
        if(!deq.empty())
        {
            sol=ps[i]-ps[deq.front()];
            if(sol>=0)
                return 1;
        }
    }
    return 0;
}