Cod sursa(job #2522030)

Utilizator CharacterMeCharacter Me CharacterMe Data 11 ianuarie 2020 21:06:41
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
std::ifstream fin("secv3.in");
std::ofstream fout("secv3.out");
int n, l, u, cnt;
double left, right, mid, sum;
std::pair<double, double> list[30005];
double numbers[30005], sums[30005];
std::queue<double> q;
bool check(double val);
int main()
{
    fin>>n>>l>>u;
    for(int i=1; i<=n; ++i) fin>>list[i].first;
    for(int i=1; i<=n; ++i) fin>>list[i].second;
    left=0.0, right=1000.0;
    for(int k=1; k<=100; ++k){
        mid=(left+right)/2;
        if(check(mid)) left=mid;
        else right=mid;
    }
    fout<<std::fixed<<std::setprecision(2)<<left<<"\n";
    return 0;
}
bool check(double val){
    for(int i=1; i<=n; ++i) numbers[i]=list[i].first-list[i].second*val;
    cnt=0;
    for(int i=1; i<=n; ++i){
        sums[i]=sums[i-1]+numbers[i];
        ++cnt;
        if(l+cnt>u){
            --cnt;
            sums[i]-=numbers[i-cnt];
        }
        while(sums[i]<0.0){
            --cnt;
            sums[i]-=numbers[i-cnt];
        }
    }
    sum=0;
    for(int i=1; i<l; ++i) sum+=numbers[i];
    for(int i=l; i<=n; ++i){
        sum+=numbers[i];
        sum-=numbers[i-l];
        if(sum+sums[i-l]>=0) return true;
    }
    return false;
}