Pagini recente » Cod sursa (job #2333397) | Cod sursa (job #566370) | Cod sursa (job #2691341) | Cod sursa (job #620041) | Cod sursa (job #3142255)
#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;
}