Cod sursa(job #2497548)

Utilizator raulsomesanRaul Somesan raulsomesan Data 22 noiembrie 2019 20:29:39
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;
const double eps = 0.001;
int v[30001],t[30001];
int l,u,n;
double aux[30001];
deque <int> d;
bool OK(double x){
    d.clear();
    aux[0] = 0;
    for(int i = 1;i <= n;i++){
        aux[i] = v[i] - t[i] * x;
        aux[i] += aux[i-1];
        if(i >= l){
            while(!d.empty() && aux[d.back()] >= aux[i - l]){
                d.pop_back();
            }
            while(!d.empty() && d.front() == i - u + 1){
                d.pop_front();
            }
            d.push_back(i - l);
            if( aux[i] - aux[d.front()] >= 0)
                return 1;
        }
    }
    return 0;
}
int main()
{
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");
    cin >> n >> l >> u;
    for(int i = 1;i <= n;i++){
        cin >> v[i];
    }
    for(int i = 1;i <= n;i++){
        cin >> t[i];
    }
    double r = 0,pas = (1 << 20);
    while(pas > eps){
        if(OK(r + pas)){
            r += pas;
        }
        pas /= 2;
    }
    cout << r;
    return 0;
}