Cod sursa(job #2829836)

Utilizator DordeDorde Matei Dorde Data 9 ianuarie 2022 00:34:00
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<bits/stdc++.h>
#define db double
#define prec 0.01
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int const N = 30001;
deque<pair<int , int>> d;
int n , l , u;
int c[N] , t[N];
bool ok(db x){
    vector<db> v(n + 1);
    for(int i = 1 ; i <= n ; ++ i)
        v[i] = (db)c[i] - x * t[i];
    deque<db> d;
    db sum = 0.0;
    for(int i = 1 ; i <= n ; ++ i){
        d.push_back(v[i]);
        sum += v[i];
        while(d.size() > u){
            sum -= d.front();
            d.pop_front();
        }
        while(d.size() > l && d.front() < 0){
            sum -= d.front();
            d.pop_front();
        }
        if(sum > 0.0)
            return true;
    }
    return false;
}
int main()
{
    fin >> n >> l >> u;
    for(int i = 1 ; i <= n ; ++ i)
        fin >> c[i];
    for(int i = 1 ; i <= n ; ++ i)
        fin >> t[i];
    db st = 0.001 , dr = 1000.0 , ans;
    while(dr - st > prec){
        db mid = (st + dr) / 2;
        if(ok(mid)){
            ans = mid;
            st = mid + prec;
        }
        else
            dr = mid - prec;
    }
    fout << fixed << setprecision(2) << ans << '\n';
    return 0;
}