Pagini recente » Cod sursa (job #751784) | Cod sursa (job #2304544) | Cod sursa (job #156302) | Cod sursa (job #1174389) | Cod sursa (job #741853)
Cod sursa(job #741853)
#include <stdio.h>
#define MAXN 400001
int A[MAXN], Deque[MAXN];
long long S[MAXN], Maxim;
int N, st, dr;
int i, front, back, x, y;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&N);
for (i=1; i<=N; ++i){
scanf("%d %d",&x,&y);
if (y == 0) x = -x;
A[i] = x;
A[i+N] = x;
}
for (i=1; i<=2*N; ++i)
S[i] = S[i-1] + A[i];
front = 1; back = 0; Maxim = S[N]; st = 1; dr = N;
for (i=1; i <= 2*N; ++i){
while (front <= back && Deque[front] < i - N)
++front;
if (Maxim < S[i] - S[Deque[front]]){
Maxim = S[i] - S[Deque[front]];
st = Deque[front] + 1;
dr = i;
}
while (front <= back && S[Deque[back]] > S[i])
--back;
Deque[++back] = i;
}
printf("%lld %d %d\n", Maxim, st, dr-st+1);
return 0;
}