Cod sursa(job #3222755)

Utilizator SSKMFSS KMF SSKMF Data 11 aprilie 2024 16:14:03
Problema Secventa 3 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;

ifstream cin ("secv3.in");
ofstream cout ("secv3.out");

int Cmmdc (const int valoare_1 , const int valoare_2)
{
    return valoare_2 ? Cmmdc(valoare_2 , valoare_1 % valoare_2) : valoare_1;
}

struct Fractie {
    pair <int , int> valoare;
    Fractie () { valoare = {0 , 1}; }
    Fractie (const pair <int , int> _valoare) { 
        const int impartitor = Cmmdc(_valoare.first , _valoare.second);
        valoare = {_valoare.first / impartitor , _valoare.second / impartitor};
    }
    ~Fractie () { }

    bool operator < (const Fractie optiune) const 
        { return (*this).valoare.first * optiune.valoare.second < (int64_t)optiune.valoare.first * (*this).valoare.second; }
    bool operator <= (const Fractie optiune) const 
        { return (*this).valoare.first * optiune.valoare.second <= (int64_t)optiune.valoare.first * (*this).valoare.second; }
};

int suma[2][30001];

int main ()
{
    int lungime , lungime_minima , lungime_maxima;
    cin >> lungime >> lungime_minima >> lungime_maxima;

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> suma[0][indice]; suma[0][indice] += suma[0][indice - 1]; }

    for (int indice = 1 ; indice <= lungime ; indice++)
        { cin >> suma[1][indice]; suma[1][indice] += suma[1][indice - 1]; }

    Fractie maxim;
    deque < pair <Fractie , int> > candidati;
    for (int indice = lungime_minima ; indice <= lungime ; indice++)
    {
        Fractie actual({suma[0][indice] - suma[0][indice - lungime_minima] , suma[1][indice] - suma[1][indice - lungime_minima]});
        while (!candidati.empty() && candidati.back().first < actual)
            { candidati.pop_back(); }

        candidati.push_back({actual , indice});
        if (candidati.front().second == indice - lungime_maxima)
            { candidati.pop_front(); }

        maxim = max(maxim , candidati.front().first);
    }

    cout << fixed << setprecision(2) << (long double)maxim.valoare.first / maxim.valoare.second;
    cout.close(); cin.close();
    return 0;
}