Pagini recente » Cod sursa (job #2259008) | Cod sursa (job #1023851) | Diferente pentru implica-te/arhiva-educationala intre reviziile 102 si 101 | Cod sursa (job #2901271) | Cod sursa (job #24531)
Cod sursa(job #24531)
#include <stdio.h>
#define MAX_N 200005
#define FIN "buline.in"
#define FOUT "buline.out"
int N, A[MAX_N], S, P, L, sum[MAX_N], pos[MAX_N];
int main(void)
{
int i, a, b, s, p;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
{
scanf("%d %d", &a, &b);
A[i] = a*(b ? +1 : -1);
}
S = s = A[N]; P = p = N; L = 1;
for (i = N-1; i > 0; i--)
{
s += A[i];
if (s <= A[i]) s = A[i], p = i;
if (S <= s) S = s, P = i, L = p-i+1;
}
for (i = 1; i <= N; i++)
sum[i] = sum[i-1]+A[i];
for (pos[1] = 1, i = 2; i <= N; i++)
{
pos[i] = pos[i-1];
if (sum[pos[i]] < sum[i]) pos[i] = i;
}
for (s = 0, i = N; i > 0; i--)
{
s += A[i]; p = s+sum[pos[i-1]];
if (S < p || (S == p && P > i))
S = p, P = i, L = N-i+1+pos[i-1];
}
printf("%d %d %d\n", S, P, L);
return 0;
}