Pagini recente » Cod sursa (job #2067728) | Cod sursa (job #1722653) | Cod sursa (job #2532758) | Cod sursa (job #746840) | Cod sursa (job #26757)
Cod sursa(job #26757)
#include <cstdio>
using namespace std;
const char iname[] = "buline.in";
const char oname[] = "buline.out";
#define MAX_N 200005
int A[MAX_N], S[MAX_N], T[MAX_N], P[MAX_N];
int main(void) {
freopen(iname, "r", stdin);
int n;
int i;
int color;
for (scanf("%d", & n), i = 1; i <= n; ++ i) {
scanf("%d %d", A + i, & color);
if (color == 0)
A[i] = - A[i];
S[i] = S[i - 1] + A[i];
T[i] = T[i - 1], P[i] = P[i - 1];
if (T[i] < S[i])
T[i] = S[i], P[i] = i;
}
int res = A[1];
int start = 1;
int length = 1;
int sum = 0;
int p = 0;
for (i = 1; i <= n; ++ i) {
if (sum > 0)
sum = sum + A[i];
else
sum = A[i], p = i;
if (res < sum)
res = sum, start = p, length = i - p + 1;
}
for (i = 1; i <= n; ++ i) {
if (res < S[n] - S[i - 1] + T[i - 1])
res = S[n] - S[i - 1] + T[i - 1], start = i, length = P[i - 1] + n - i + 1;
}
freopen(oname, "w", stdout);
printf("%d %d %d\n", res, start, length);
return 0;
}