Pagini recente » Cod sursa (job #606554) | Cod sursa (job #2036947) | Cod sursa (job #1506857) | Cod sursa (job #2843512) | Cod sursa (job #1337351)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#define Nmax 400005
#define Inf 2000000000
using namespace std;
deque < int >e;
int n,i,j,sol,p,q,nr,v[Nmax*2],s[2*Nmax];
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n); sol=-Inf;
for (i=1;i<=n;i++)
{
scanf("%d %d",&v[i],&p);
if (p==0) v[i]=-v[i];
}
p=0;
for (i=1;i<n;i++) v[i+n]=v[i];
s.push_front(0);
for (i=1;i<=2*n-1;i++)
{
s[i]=s[i-1]+v[i];
while ((!e.empty())&&(s[e.back()]>s[i]))
e.pop_back();
e.push_back(i);
if (i-e.front()>n) e.pop_front();
if (s[e.front()]>0)
{
if (s[i]>=sol && i<=n)
{sol=s[i],p=1,q=i;
continue;}
}
if (s[i]-s[e.front()]>=sol)
sol=s[i]-s[e.front()],p=e.front()+1,q=i-e.front();
}
printf("%d %d %d",sol,p,q);
return 0;
}