Pagini recente » Cod sursa (job #664854) | Cod sursa (job #647362) | Cod sursa (job #1619328) | Cod sursa (job #566597) | Cod sursa (job #26126)
Cod sursa(job #26126)
#include <stdio.h>
#define FIN "buline.in"
#define FOUT "buline.out"
#define MAX 200001
#define inf 0x3f3f3f
long A[MAX], S[MAX], T[MAX][2];
long N;
long Max = -inf, PM=inf, LM = inf;
int main() {
long i, x, st = 1, fi=1;
freopen(FIN, "r", stdin);
scanf("%ld", &N);
long Sum = 0;
S[0] = 0; T[0][0] = -inf;
for (i=1; i<=N; ++i) {
scanf("%ld %ld", A+i, &x);
if ( x==0 )
A[i] *= -1;
S[i] = S[i-1] + A[i];
if ( T[i-1][0] < S[i] ) {
T[i][0] = S[i];
T[i][1] = i;
}
else {
T[i][0] = T[i-1][0];
T[i][1] = T[i-1][1];
}
if ( Sum + A[i] > A[i] ) {
Sum += A[i], fi = i;
}
else {
Sum = A[i]; fi = i; st = i;
}
if ( Max < Sum )
Max = Sum, PM = inf, LM = inf;
if ( Max == Sum ) {
if ( PM > st )
PM=st;
if ( PM==st && LM > fi-st+1 )
LM = fi-st+1;
}
}
fclose(stdin);
for (i=2; i<=N; ++i) {
if ( Max < S[N] - S[i-1] + T[i-1][0] )
Max = S[N] - S[i-1] + T[i-1][0], PM = inf, LM = inf;
if ( Max == S[N] - S[i-1] + T[i-1][0] ) {
if ( PM > i )
PM = i;
if ( PM==i && LM > T[i][1] + N-i+1)
LM = T[i][1] + N-i+1;
}
}
freopen(FOUT, "w", stdout);
printf("%ld %ld %ld\n", Max, PM, LM);
fclose(stdout);
return 0;
}