Cod sursa(job #1834541)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 24 decembrie 2016 18:54:34
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <queue>
using namespace std;
const int BSLIM = 100000;
int n,l,u,i,v[30005],w[30005];
long long p[30001];
void build_array(int x)
{
    int i;
    for(i=1; i<=n; i++)
    {
        p[i]=p[i-1]+v[i]*100-x*w[i];
    }
}
bool bs_check(int X)
{
    int i;
    deque <long long> q;
    build_array(X);
    for(i=1; i<=n; i++)
    {
        if(!q.empty()&&q.front()<i-u)
        {
            q.pop_front();
        }
        if(i-l>=0)
        {
            while(!q.empty()&&p[i-l]<=p[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i-l);
        }
        if(!q.empty())
        {
            if(p[i]-p[q.front()]>=0) return 1;
        }
    }
    return 0;
}
int b_search()
{
    int st=1,dr=100000,m,best=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(bs_check(m)==1)
        {
            best=m;
            st=m+1;
        }
        else dr=m-1;
    }
    return best;
}
int main()
{
    ifstream f("secv3.in");
    ofstream g("secv3.out");
    f>>n>>l>>u;
    for(i=1; i<=n; i++) f>>v[i];
    for(i=1; i<=n; i++) f>>w[i];
    g<<(double)b_search()/100<< '\n';
    f.close(); g.close();
    return 0;
}