Cod sursa(job #2445408)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 3 august 2019 22:22:23
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream cin("secv3.in");
ofstream cout("secv3.out");

int n,l,u,sol;
long long c[30005],t[30005],r[30005];
deque<int> d;
int begin,end,middle;

long long ans(int x){

    long long Max=-3e14;

    for(int i=1;i<=n;i++)
        r[i]=c[i]-t[i]*x;

    for(int i=l;i<=n;i++){

        while(!d.empty() && r[d.back()]>r[i-l]) d.pop_back();
        d.push_back(i-l);

        Max=max(Max,r[i]-r[d.front()]);

        if(d.front()==i-u) d.pop_front();

    }

    d.clear();

    return Max;

}

int main(){

    cin>>n>>l>>u;
    for(int i=1;i<=n;i++) {int x; cin>>x; c[i]=c[i-1]+100*x;}
    for(int i=1;i<=n;i++) {int x; cin>>x; t[i]=t[i-1]+x;}

    begin=0; end=100000;

    while(end-begin>1){

        middle=(begin+end)/2;
        if(ans(middle)>=0){
            sol=middle;
            begin=middle;
        }
        else end=middle;

    }

    cout<<sol/100.0;

}