Cod sursa(job #3163885)

Utilizator SSKMFSS KMF SSKMF Data 1 noiembrie 2023 15:33:34
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <deque>
using namespace std;

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

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

    int factor[2][30001];
    for (int indice_1 = 0 ; indice_1 < 2 ; indice_1++) {
        factor[indice_1][0] = 0;
        for (int indice_2 = 1 ; indice_2 <= lungime_totala ; indice_2++) {
            cin >> factor[indice_1][indice_2]; factor[indice_1][indice_2] += factor[indice_1][indice_2 - 1];
        }
    }

    deque <int> optiuni;
    pair <int , int> maxim = make_pair(0 , 1);
    for (int indice = lungime_minima ; indice <= lungime_totala ; indice++)
    {
        optiuni.push_back(indice - lungime_minima);
        if (optiuni.front() == indice - lungime_maxima - 1)
            { optiuni.pop_front(); }

        while (optiuni.size() > 1) {
            const int initial = optiuni.back(); optiuni.pop_back();
            pair <int , int> optiune_1 = make_pair(factor[0][indice] - factor[0][initial] , factor[1][indice] - factor[1][initial]);
            pair <int , int> optiune_2 = make_pair(factor[0][indice] - factor[0][optiuni.back()] , factor[1][indice] - factor[1][optiuni.back()]);
            if (1LL * optiune_1.first * optiune_2.second < 1LL * optiune_2.first * optiune_1.second) { optiuni.push_back(initial); break; }
        }

        pair <int , int> actual = make_pair(factor[0][indice] - factor[0][optiuni.back()] , factor[1][indice] - factor[1][optiuni.back()]);
        if (1LL * maxim.first * actual.second < 1LL * actual.first * maxim.second) { maxim = actual; }
    }

    cout << maxim.first / maxim.second << '.' << 100 * maxim.first / maxim.second % 100;
    cout.close(); cin.close();
    return 0;
}