Cod sursa(job #2305257)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 19 decembrie 2018 18:50:01
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");
int const NMAX = 30003;
double const eps = 0.00001;
int timp [NMAX + 3], cost [NMAX + 3];
int N, L, U;
double ans, pls;
double V [NMAX + 3], sp [NMAX + 3], poz [NMAX + 3];
bool valid (double X){
    deque <int> Diqu;
    for (int i = 1 ; i <= N ; i ++)V [i] = timp [i] - cost [i] * X;
    for (int i = 1 ; i <= N ; i ++)sp [i] = sp [i - 1] + V [i];
    for (int i = 1 ; i <= N ; i ++){
        while (0 < Diqu.size () && sp [i] <= sp [Diqu.back ()])
            Diqu.pop_back ();
        Diqu.push_back (i);
        while (0 < Diqu.size () && Diqu.front () <= i - U + L - 1)
            Diqu.pop_front ();
        poz [i] = sp [Diqu.front()];
    }
    for (int i = 1 ; i <= N - L ; i ++)
        if (sp [i + L] - poz [i] >= 0)return 1;
    return 0;
}
int main (){
    fin >> N >> L >> U;
    for (int i = 1 ; i <= N ; i ++)fin >> timp [i];
    for (int i = 1 ; i <= N ; i ++)fin >> cost [i];
    for (pls = (1 << 21) ; eps < pls; pls /= 2)
        if (valid (ans + pls))ans += pls;
    fout << ans;
    return 0;
}