Cod sursa(job #1458128)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 6 iulie 2015 23:27:50
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int SHIFT = 100;

int n , L , R , i;
vector < int > x , y;
vector < long long > dp;

deque < int > dq;

bool check(int val)
{
    /// Sx / Sy = val   =>    Sx - val * Sy = 0   =>    daca Sx - val * Sy >= 0  - exista solutia val

    int i; dq.clear();

    for (i = 1; i <= n; ++i)
        dp[i] = dp[i-1] + x[i] * SHIFT - y[i] * val;

    for (i = L; i <= n; ++i)
    {
        while (dq.size() && dp[dq.back()] >= dp[i-L])
            dq.pop_back();

        dq.push_back(i-L);

        if (i - dq.front() > R)
            dq.pop_front();

        if ((dp[i] - dp[dq.front()]) >= 0)
            return 1;
    }

    return 0;
}

float Binary_Search()
{
    int i , step , N = 1000 * SHIFT;

    for (step = 1; step < N; step <<= 1);

    for (i = 0; step; step >>= 1)
        if (i + step <= N && check(i + step))
            i += step;

    return 1.0 * i / SHIFT;
}

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

    scanf("%d %d %d", &n, &L, &R);
    x = vector < int > (n + 1); y = vector < int > (n + 1); dp = vector < long long > (n + 1);

    for (i = 1; i <= n; ++i)
        scanf("%d", &x[i]);

    for (i = 1; i <= n; ++i)
        scanf("%d", &y[i]);

    printf("%.2f", Binary_Search());

    return 0;
}