Cod sursa(job #997585)

Utilizator poptibiPop Tiberiu poptibi Data 14 septembrie 2013 16:41:21
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;

const int NMAX = 30005;
const double EPS = 1e-7;

int N, L, U, C[NMAX], T[NMAX];
double V[NMAX], S[NMAX];
deque<int> D;

int Check(double M)
{
    for(int i = 1; i <= N; ++ i)
    {
        V[i] = C[i] - M * T[i];
        S[i] = S[i - 1] + V[i];
    }

    D.clear();

    for(int i = L; i <= N; ++ i)
    {
        while(!D.empty() && S[i - L] < S[D.back()]) D.pop_back();
        D.push_back(i - L);
        while(!D.empty() && D.front() < i - U) D.pop_front();
        if(!D.empty() && S[i] >= S[D.front()]) return i;
    }
    return 0;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);

    scanf("%i %i %i", &N, &L, &U);
    for(int i = 1; i <= N; ++ i)
        scanf("%i", &C[i]);
    for(int i = 1; i <= N; ++ i)
        scanf("%i", &T[i]);

    double Left = 0.0, Right = 1000.0, Mid, Ans;
    while(fabs(Right - Left) > EPS)
    {
        Mid = (Left + Right) / 2;
        if(Check(Mid)) Ans = Mid, Left = Mid;
        else Right = Mid;
    }

    printf("%.2f\n", Ans);

    return 0;
}