Cod sursa(job #2631558)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 30 iunie 2020 14:22:23
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 30000;
const double EPS=1e-3;
int n, l, u, c[nmax + 5], t[nmax + 5], spc[nmax + 5], spt[nmax + 5];
double a[nmax + 5];
deque <int> d;

bool Check(double mid)
{
    d.clear();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = (double)spc[i] - (double)(spt[i] * mid);
    }
    for (int i = l; i <= n; ++i)
    {
        if(d.size() > 0 && d.front() < i - u) d.pop_front();
        while (d.size() > 0 && a[i - l] <= a[d.back()]) d.pop_back();
        d.push_back(i - l);
        if (a[i] - a[d.front()] >= 0) return true;
    }
    return false;
}

int main()
{
    fin >> n >> l >> u;
    for (int i = 1; i <= n; ++i)
    {
        fin >> c[i];
        spc[i] = c[i] + spc[i - 1];
    }
    for (int i = 1; i <= n; ++i)
    {
        fin >> t[i];
        spt[i] = t[i] + spt[i - 1];
    }
   double st = 0, dr = 1000, last = 0;
    while(dr - st >= EPS) {
        double mij = (st + dr) / 2;
        if(Check(mij) == 1) {
            st = mij;
            last = mij;
        }
        else {
            dr = mij;
        }
    }
    fout << fixed << setprecision(2) << last << "\n";
    fin.close();
    fout.close();
    return 0;
}