Cod sursa(job #3142255)

Utilizator SSKMFSS KMF SSKMF Data 20 iulie 2023 13:06:04
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <deque>
using namespace std;

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

long long suma[400001];

int main ()
{
    int lungime;
    cin >> lungime;

    for (int indice = 1 , tip ; indice <= lungime ; indice++) {
        cin >> suma[indice] >> tip;
        if (tip == 1) suma[indice + lungime] = suma[indice];
        else suma[indice + lungime] = (suma[indice] *= -1);
    } 

    deque <int> optiuni; optiuni.push_back(0);
    long long suma_maxima = suma[1] , inceput = 1 , lungime_secventa = 1;
    for (int indice = 1 , limita = (lungime << 1) ; indice <= limita ; indice++) {
        suma[indice] += suma[indice - 1];
        if (suma[indice] - suma[optiuni.front()] > suma_maxima) {
            suma_maxima = suma[indice] - suma[optiuni.front()];
            lungime_secventa = indice - optiuni.front();
            inceput = optiuni.front() + 1;
        }

        while (!optiuni.empty() && suma[indice] <= suma[optiuni.back()])
            optiuni.pop_back();

        optiuni.push_back(indice);

        if (optiuni.front() == indice - lungime)
            optiuni.pop_front();
    }    

    cout << suma_maxima << ' ' << inceput << ' ' << lungime_secventa;
    cout.close(); cin.close();
    return 0;
}