Pagini recente » Cod sursa (job #2744829) | Cod sursa (job #1526072) | Cod sursa (job #2434656) | Cod sursa (job #622667) | Cod sursa (job #64814)
Cod sursa(job #64814)
#include<stdio.h>
int a[200001],b[200001],n,x,y,j,i,que[200001],s,start,end,max,ss,frcv[200001],poz,lung;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
{
scanf("%ld %ld",&x,&y);
if (y==0) a[i]=-x;
else a[i]=x;
}
for(i=2;i<=n;i++)
b[i]=b[i-1]+a[i];
s=b[n]+a[1];
que[0]=-200001;
que[1]=b[2];
start=1;
end=1;
for(i=3;i<=n;i++)
{
while(b[i]<que[end]) end--;
end++;
que[end]=b[i];
frcv[end]=i;
}
max=s;
if (max<s-que[1]) max=s-que[1];
i=2;
b[1]=s;
while (i<=n)
{
if (que[start]==b[i]) start++;
ss+=b[i];
if (i>2)
b[i-1]=b[i-2]+a[i-1];
while(b[i-1]<que[end]) end--;
end++;
que[end]=b[i-1];
frcv[end]=i-1;
if (s-que[start]+ss>max)
{
max=s-que[start]+ss;
poz=frcv[start]+1;
if (i-poz<0)
lung=i+n-poz+1;
else
lung=i-poz+1;
}
i++;
}
printf("%ld %ld %ld",max,poz,lung);
return 0;
}