Pagini recente » Cod sursa (job #2261135) | Cod sursa (job #2507424) | Cod sursa (job #363834) | Cod sursa (job #1182800) | Cod sursa (job #491220)
Cod sursa(job #491220)
#include<cstdio>
#define N 1<<18
int max,pi,pf,st,dr,n,k,a[N],s[N],dq[N];
void read()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
int x,c;
scanf("%d",&n);
k=n+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&c);
if(c==0)
{
a[i]=a[n+i]=-x;
continue;
}
a[i]=a[n+i]=x;
}
n=2*n;
}
void init()
{
for(int i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
}
void elimst(int poz)
{
if(poz-dq[st]>=k)
st++;
}
void elimdr(int poz)
{
while(s[dq[dr]]>s[poz] && dr>st)
dq[dr]=0,dr--;
dq[++dr]=poz;
}
void solve()
{
max=-200000;
dq[++st]=1;
dr=1;
for(int i=2;i<=n;i++)
{
elimst(i);
if(s[i]-s[dq[st]]>max)
{
max=s[i]-s[dq[st]];
pi=dq[st];
pf=i;
}
elimdr(i);
}
printf("%d %d %d",max,pi+1,pf-pi);
}
int main()
{
read();
init();
solve();
return 0;
}