Cod sursa(job #166570)
//buline - IA
#include <stdio.h>
long long int n, a, b, s[400004], deque[400004], qbegin, qend, max = -10001;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
int i, pi, pf;
scanf("%lld",&n);
for (i = 1; i <= n; i++)
{
scanf("%lld %lld",&s[i], &a);
if (!a) s[i] *= (-1);
s[i + n] = s[i];
}
for (i = 1; i <= 2 * n; i++) s[i] = s[i - 1] + s[i];
qbegin = 1;
for (i = 1; i <= 2 * n; i++)
{
qend++;
while (qend > qbegin && s[deque[qend-1]] > s[i - a]) qend--;
deque[qend] = i - 1;
if (deque[qbegin] < i - n) qbegin++;
if (s[i] - s[deque[qbegin]] > max)
{
max = s[i] - s[deque[qbegin]];
pi = deque[qbegin]+1;
pf = i;
}
}
printf("%lld %lld %lld\n",max,pi,pf - pi + 1);
return 0;
}