Pagini recente » Cod sursa (job #552860) | Cod sursa (job #3197507) | Cod sursa (job #578925) | Cod sursa (job #3238069) | Cod sursa (job #3142259)
#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;
}