Cod sursa(job #3142259)

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

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

class deque {
    private:
        int valori[1000001] , stanga , dreapta;
    public:
        deque () { stanga = 5e5 + 1; dreapta = 5e5; }
        ~deque () { }

        int front () { return valori[stanga]; }
        int back () { return valori[dreapta]; }
        bool empty () { return dreapta - stanga + 1 == 0; }
        void push_back (const int valoare) { 
            if ((*this).empty())
                stanga = dreapta + 1;
            
            valori[++dreapta] = valoare;
        }
        void push_front (const int valoare) {
            if ((*this).empty())
                dreapta = stanga - 1;
            
            valori[--stanga] = valoare;
        }
        void pop_front () { stanga++; }
        void pop_back () { dreapta--; } 
} optiuni;

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);
    } 

    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;
}