Cod sursa(job #2194329)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 12 aprilie 2018 21:35:23
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<queue>
#include<iomanip>
using namespace std;
ifstream fi("secv3.in");
ofstream fo("secv3.out");
int n,l,u,A[30005],B[30005],Minim[30005],i,rez;
long long V[30005];
deque<int> Q;

bool check(int x)
{
    Q.clear();
    int i;
    for(i=1; i<=n; i++)
        V[i]=V[i-1]+A[i]-x*B[i];
    for(i=1; i<=n; i++)
    {
        if(!Q.empty() && i-Q.front()>=(u-l+1))
            Q.pop_front();
        while(!Q.empty() && V[i]<V[Q.back()])
            Q.pop_back();
        Q.push_back(i);
        Minim[i]=Q.front();
    }
    if(l==u)
        for(i=1; i<=n; i++)
            Minim[i]=V[i];
    for(i=l; i<=n; i++)
    {
        if(V[i]-V[Minim[i-l]]>=0)
            return 1;
        if(i<=u && V[i]>=0)
            return 1;
    }
    return 0;
}

int main()
{
    fi>>n>>l>>u;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
        A[i]*=100;
    }
    for(i=1; i<=n; i++)
        fi>>B[i];
    rez=0;
    for(i=16; i>=0; i--)
        if(check(rez+(1<<i)))
            rez=rez+(1<<i);
    fo<<setprecision(2)<<fixed<<(rez/100.0)<<"\n";
    fi.close();
    fo.close();
    return 0;
}