Pagini recente » Cod sursa (job #1069252) | Cod sursa (job #2941083) | Cod sursa (job #2151663) | Cod sursa (job #205994) | Cod sursa (job #2098117)
#include <fstream>
#define DEF 200010
#define INF 1 << 29
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int n, v[2 * DEF], s[2 * DEF], h[2 * DEF], Min, Max = -INF, st, dr, p, l;
int main() {
fin >> n;
for (int i = 1; i <= n; ++ i) {
int temp;
fin >> v[i] >> temp;
if (!temp) {
v[i] *= -1;
}
}
for (int i = 1; i < n; ++ i) {
v[i + n] = v[i];
}
s[1] = v[1];
h[++ dr] = 1;
Min = INF;
for (int i = 2; i < 2 * n; ++ i) {
s[i] = s[i - 1] + v[i];
Min = s[h[st]];
int temp = s[i] - Min;
if (temp > Max) {
Max = temp;
p = h[st] + 1;
l = i - p + 1;
}
while (st <= dr && s[i] < s[h[dr]]) {
-- dr;
}
h[++ dr] = i;
if (h[st] < i - n + 1)
++ st;
}
fout << Max << " " << p << " " << l;
return 0;
}