Cod sursa(job #2703767)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 9 februarie 2021 10:59:00
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int NMAX = 3e4 + 3;
int N, L, U;
double sum[NMAX];
pair<double,double> a[NMAX];

double check(const double &x) {
    deque<int> Q;
    for(int i = 1; i <= N; ++i) {
        sum[i] = sum[i - 1] + a[i].first - x * a[i].second;
        while(!Q.empty() && Q.front() < i - U)
            Q.pop_front();
        if(i >= L) {
            while(!Q.empty() && sum[Q.back()] > sum[i - L])
                Q.pop_back();
            Q.emplace_back(i - L);
            if(sum[i] - sum[Q.front()] >= 0)
                return true;
        }
    }
    return false;
}

int main() {
    fin >> N >> L >> U;
    for(int i = 1; i <= N; ++i)
        fin >> a[i].first;
    for(int i = 1; i <= N; ++i)
        fin >> a[i].second;
    double st = 0, dr = 1000, ans = 0;
    for(int itr = 0; itr < 16; ++itr) {
        double mid = (st + dr) / 2;
        if(check(mid)) {
            ans = mid;
            st = mid;
        }
        else
            dr = mid;
    }
    fout << fixed << setprecision(2) << ans << '\n';
}