Cod sursa(job #1452278)

Utilizator ZenusTudor Costin Razvan Zenus Data 20 iunie 2015 14:55:16
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <cstring>
#include <iomanip>

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int NSIZE = 30000 + 10;

deque < int > inDeque;
int d[NSIZE] , x[NSIZE] , y[NSIZE];
int bsl , bsr , k , f , le , ri , N , i;

bool check(int k)
{
    memset(d,0,sizeof(d));
    while (inDeque.size()) inDeque.pop_back();

    for (i = 1 ; i <= N ; ++i)
    d[i] = d[i - 1] + x[i] - y[i] * k;

    for (i = le ; i <= N ; ++i)
    {
        while (inDeque.size() && d[i - le] <= d[inDeque.back()])
        inDeque.pop_back();

        inDeque.push_back(i - le);

        while (inDeque.front() < i - ri)
        inDeque.pop_front();

        if (d[i] - d[inDeque.front()] >= 0) return true;
    }

    return false;
}

int main()
{

fin >> N >> le >> ri;

for (i = 1 ; i <= N ; ++i)
{
    fin >> x[i];
    x[i] *= 100;
}

for (i = 1 ; i <= N ; ++i)
fin >> y[i];

bsl = 0 , bsr = 100000;

while (bsl <= bsr)
{
    int k = (bsl + bsr) >> 1;

    if (check(k))
    {
        bsl = k + 1;
        f = k;
    } else bsr = k - 1;
}

fout << setprecision(3) << fixed << 1.0 * f / 100 << '\n';

return 0;
}