Pagini recente » Cod sursa (job #175987) | Cod sursa (job #3285445) | Cod sursa (job #1527418) | Cod sursa (job #368544) | Cod sursa (job #1106197)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("buline.in");
ofstream g ("buline.out");
int n;
int st, dr, front, back;
int v[400005], s[400005], dq[400005];
void citeste () {
int x, semn;
f >> n;
for (int i = 1 ; i <= n; i++) {
f >> x >> semn;
if (semn) v[i] = x;
else v[i] = -x;
v[i + n] = v[i];
}
x = 2 * n;
for (int i = 1; i <= x; i++) {
s[i] = s[i - 1] + v[i];
}
}
void rezolva () {
int maxim = s[n], l = 2 * n;
st = 1;
dr = n;
front = 1; back = 0;
for (int i = 1; i <= l; i++) {
while (front <= back && s[i] < s[dq[back]]) back--;
dq[++back] = i;
if (dq[front] == i - n) front++;
if (maxim < s[i] - s[dq[front]]) {
maxim = s[i] - s[dq[front]];
st = dq[front] + 1;
dr = i;
}
}
g << maxim << ' ' << st << ' ' << dr - st + 1 << '\n';
}
int main () {
citeste ();
rezolva ();
return 0;
}