Cod sursa(job #2404850)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 13 aprilie 2019 14:41:49
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <iomanip>
#include <deque>

using namespace std;

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

const int NMAX = 30000;

int N, L, R;
int c[NMAX + 5], t[NMAX + 5];

double s[NMAX + 5];

bool isOk(double x)
{
    for(int i = 1; i <= N; i++)
    {
        s[i] = c[i] - x * t[i];
        s[i] += s[i - 1];
    }

    deque <int> deq;

    for(int i = L; i <= N; i++)
    {
        while(!deq.empty() && s[deq.back()] >= s[i - L])
            deq.pop_back();
        deq.push_back(i - L);

        if(i - deq.front() == R + 1)
            deq.pop_front();

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

    return false;
}

int main()
{
    fin >> N >> L >> R;

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

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

    double st = 1e-3, dr = 3e7, mid, sol;

    for(int iteratii = 1; iteratii <= 100; iteratii++)
    {
        mid = (st + dr) / 2;

        if(isOk(mid))
        {
            sol = mid;
            st = mid + 1e-3;
        }
        else
            dr = mid - 1e-3;
    }

    fout << fixed << setprecision(6) << sol << '\n';

    return 0;
}