Cod sursa(job #2432682)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 24 iunie 2019 18:53:37
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "secv3";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 30005;

ld v[nmax], c[nmax], w[nmax];
ll n, l, r;

bool check(ld k)
{
    for (int i = 1; i <= n; ++i)
        w[i] = w[i-1]+v[i]-c[i]*k;
    deque<int> q;
    int sz = r-l+1;
    for (int i = 0; i+l <= n; ++i){
        if(!q.empty() && i-q.front() >= sz)
            q.pop_front();
        while(!q.empty() && w[q.back()] >= w[i])
            q.pop_back();
        q.push_back(i);
        if(w[i+l]-w[q.front()] >= 0)
            return 1;
    }
    return 0;
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> l >> r;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (int i = 1; i <= n; ++i)
        fin >> c[i];
    ld st = 0, dr = 1000, ans = v[1]/c[1];
    ld mid = (st+dr)/2;
    for (int t = 1; t <= 50; ++t, mid = ld(st+dr)/2.0){
        if(check(mid)){
            ans = mid;
            st = mid;
        }else dr = mid;
    }
    fout << fixed << setprecision(10) << ans << "\n";
    return 0;
}