Cod sursa(job #2438263)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 11 iulie 2019 21:48:43
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
// Matteo Verzotti - C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <ctime>
#include <map>
#include <chrono>
#include <cmath>
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a<b ? a:b
#define ld long double

using namespace std;

const int N = 30000;
const ld eps = 0.01;

int V[5 + N];
int S[5 + N];
ld aux[5 + N];
deque <int> dq;

int l, u, n;

bool ok(ld pas)
{
    ld x;
    dq.clear();
    for(int i=1; i<=n; i++){
        x = V[i] - S[i] * pas;
        aux[i] = aux[i-1] + x;
        if(i >= l){
            // incepe deque...
            while(!dq.empty()&& aux[dq.back()] >= aux[i-l])
                dq.pop_back();
            while(!dq.empty() && dq.front() <= i-u+1)
                dq.pop_front();
            dq.push_back(i-l);
            if(!dq.empty() && aux[i]-aux[dq.front()] >= 0)
                return true;
        }
    }
    return false;
}

int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    ld r, pas;
    scanf("%d%d%d", &n, &l, &u);
    for(int i=1; i<=n; i++) scanf("%d", &V[i]);
    for(int i=1; i<=n; i++) scanf("%d", &S[i]);
    pas = 1<<10;
    r = 0.00;
    while(pas >= eps){
        if(r + pas <= n && ok(r+pas))
            r += pas;
        pas /= 2;
    }
    printf("%.2Lf\n", r);
    return 0;
}