Cod sursa(job #2312220)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 4 ianuarie 2019 14:34:49
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
#define EROARE 0.001

const int MV(30005) ;

int cost[MV], timp[MV] ;
double v[MV], dp[MV], sol[MV] ;
int n, l, u ;

bool test(double val) {
    register int i ;
    for (i = 1 ; i <= n ; ++ i) {
        v[i] = cost[i] - timp[i] * val ;
        dp[i] = dp[i - 1] + v[i] ; }
    std::deque <int> dq ;
    int k = u - l + 1 ;
    dq.push_back(0) ;
    for (i = 1 ; i <= n ; ++ i) {
        while (!dq.empty() && dp[dq.back()] >= dp[i])
            dq.pop_back() ;
        dq.push_back(i) ;
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front() ;
        sol[i] = dp[dq.front()] ; }
    for (i = 1 ; i <= n ; ++ i)
        if (i >= l)
            if (sol[i - l] <= dp[i])
                return true ;
    return false ; }

int main() {
    freopen("secv3.in", "r", stdin) ;
    freopen("secv3.out", "w", stdout) ;
    register int i ;
    scanf("%d %d %d", &n, &l, &u) ;
    for (i = 1 ; i <= n ; ++ i)
        scanf("%d", cost + i) ;
    for (i = 1 ; i <= n ; ++ i)
        scanf("%d", timp + i) ;
    double step(1LL << 20), pos(0) ;
    for (step ; step > EROARE ; step /= 2) {
        if (test(pos + step) == true)
            pos += step ; }
    printf("%.2f", pos) ;
    return 0 ; }