Cod sursa(job #2403171)

Utilizator ptudortudor P ptudor Data 11 aprilie 2019 12:30:18
Problema Secventa 3 Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("secv3.in");
ofstream out("secv3.out");
int n,L,U,cost[30005],timp[30005],s[30005];
deque <int> q;
int ver(int val)
{int aux,i;
    while (!q.empty())q.pop_back();
    for (i=1;i<=n;i++)
    {
        aux=cost[i]-timp[i]*val;
        s[i]=aux+s[i-1];

        if (i-L>=0){
        while (!q.empty()&&s[i-L]<=s[q.back()])
            q.pop_back();
        q.push_back(i-L);

        while (q.front()<i-U)
            q.pop_front();

        if (!q.empty()&&(s[i]-s[q.front()]>=0))
            return 1;
        }
    }
    return 0;
}
int main()
{int i,j;
    in>>n>>L>>U;
    for (i=1;i<=n;i++)
        {in>>cost[i];cost[i]*=100;}
    for (i=1;i<=n;i++)
        in>>timp[i];

    int st=1,dr=100001,last=1,mij,ok;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        ok=ver(mij);
        if (ok==1)
            last=mij,
            st=mij+1;
        else
            dr=mij-1;
    }
    if ((last%100)>9)
        out<<last/100<<"."<<last%100<<"\n";
    else
        out<<last/100<<".0"<<last%100<<"\n";
    out.close();
    in.close();
    return 0;
}