Cod sursa(job #1757501)

Utilizator antanaAntonia Boca antana Data 15 septembrie 2016 10:25:56
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <deque>
#define EPS 0.00001
#define MAXN 30000

using namespace std;

deque <int> dq;

int n, l, u, c[MAXN], t[MAXN];
double s[MAXN];

inline bool check(double m)
{
    int i;

    for(i=0;i<n;++i)
        s[i]=s[i-1] + c[i] - t[i]*m;

    for(i=0;i<n;++i)
    {
        while(!dq.empty() && i-dq.front() > u)
            dq.pop_front();

        if(i-dq.front() >= l && s[i] - s[dq.front()] >= 0)
            return true;

        if(i-l+1>=0)
        {
            while(!dq.empty() && s[i-l+1] <=s[dq.back()])
                dq.pop_back();

            dq.push_back(i-l+1);
        }
    }

    return false;
}

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

    int i;
    double pas, ans=0;

    scanf("%d%d%d", &n, &l, &u);

    for(i=0;i<n;++i)
        scanf("%d", &c[i]);
    for(i=0;i<n;++i)
        scanf("%d", &t[i]);

    for(pas=(1<<9); pas > EPS; pas*=0.5)
        if(check(ans+pas))
            ans+=pas;

    printf("%.2lf", ans);

    return 0;
}