Cod sursa(job #490438)
/*
* File: main.cpp
* Author: petru
*
* Created on 2010-10-06
*/
#include <cstdio>
#include <deque>
#define deb(n) fprintf(stderr,"%d ",(n));
#define DN 200005
#define MULT 0x3f3f3f3f
#define LL long long
//#define int long long
using namespace std;
LL sir[DN*2],sol=-MULT;
int n;
int main()
{
int i;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; ++i) {
int op;
scanf("%lld %d",&sir[i],&op);
if(!op) sir[i]=-sir[i];
sir[i+n]=sir[i];
}
for(i=1,n*=2;i<n; ++i) sir[i]+=sir[i-1];
deque <int> d;
LL st,lg;
for(i=1; i<=n; ++i) {
for(;!d.empty() && d.front()<=i-n;d.pop_front());
for(;!d.empty() && sir[i]<sir[d.back()];d.pop_back());
d.push_back(i);
if(sir[i]-sir[d.front()]>sol) {
sol=sir[i]-sir[d.front()];
st=d.front()+1;
lg=i-d.front();
}
}
printf("%lld %lld %lld",sol,st,lg);
return 0;
}