Cod sursa(job #1892263)

Utilizator antanaAntonia Boca antana Data 24 februarie 2017 20:42:18
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia14-cautare_binara 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+1], t[MAXN+1];
double s[MAXN+1];
 
inline bool check(double m)
{
    int i;
 
    dq.clear();
 
    for(i=1;i<=n;++i)
        s[i]=s[i-1] + c[i] - t[i]*m;
 
    dq.push_back(0);
 
    for(i=l;i<=n;++i)
    {
        while(!dq.empty() && i-dq.front() > u)
            dq.pop_front();
 
        if(s[i] - s[dq.front()] >= 0)
            return true;
 
        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=1;i<=n;++i)
        scanf("%d", &c[i]);
    for(i=1;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;
}