Pagini recente » Cod sursa (job #2553348) | Cod sursa (job #2606880) | Cod sursa (job #2009426) | Cod sursa (job #795502) | Cod sursa (job #1324883)
#include<cstdio>
#include<deque>
#define NMAX 200005
using namespace std;
deque<int>d;
int x,y,smax,l,p,i,n;
int v[NMAX],sum[NMAX];
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) v[i]=v[i+n]=(-1)*x;
else v[i]=v[i+n]=x;
sum[i]=sum[i-1]+v[i];
}
for (i=n+1;i<=2*n;++i)
sum[i]=sum[i-1]+v[i];
smax=-10001;
for (i=1;i<=2*n;++i)
{
while(!d.empty() && sum[i]<=sum[d.back()])
d.pop_back();
d.push_back(i);
if (d.front()==i-n) d.pop_front();
if (smax<sum[i]-sum[d.front()])
{
smax=sum[i]-sum[d.front()];
if (i>n) {p=d.front()+1; l=i-d.front();}
else {p=d.front()+1; l=d.front()-i;}
}
}
printf("%d %d %d\n",smax,p,l);
return 0;
}