Cod sursa(job #1870462)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 6 februarie 2017 17:46:44
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

const int Max = 30007;
int n, l, u, c[Max], t[Max];

double sum2(double sayi)
{
    double v[Max], toplam[Max];
    toplam[0] = 0;
    deque<int> q;
    double sonsuz = -30000000;

    for(int i = 1; i <= n; ++i)
    {
        v[i] = c[i] - (sayi * t[i]);
        toplam[i] = toplam[i - 1] + v[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        while(!q.empty() && toplam[i - 1] <= toplam[q.back()])
            q.pop_back();
        q.push_back(i - 1);
        if(q.front() < i - u)
            q.pop_front();
        sonsuz = max(sonsuz, toplam[i] - toplam[q.front()]);
    }
    return sonsuz;
}

double cevap()
{
    double st = 0, dr = Max;
    for(int i = 1; i <= 40; ++i)
    {
        double mid = (st + dr) / 2;
        if(sum2(mid) > 0)
            st = mid;
        else
            dr = mid;
    }
    return dr;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d%d%d",&n,&l,&u);
    for(int i = 1; i <= n; ++i)
        scanf("%d",&c[i]);
    for(int i = 1; i <= n; ++i)
        scanf("%d",&t[i]);

    printf("%.2f",cevap());
}