Pagini recente » Cod sursa (job #2041217) | Cod sursa (job #660968) | Cod sursa (job #1434388) | Cod sursa (job #940367) | Cod sursa (job #238642)
Cod sursa(job #238642)
#include <stdio.h>
#define lm 200010
#define lmx 2000000000
long v[lm],p[lm],a[lm],n,i,max,x,poz,l,y;
bool b[lm];
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) v[i]=-x; else v[i]=x;
}
x=0;
max=-lmx;
for (i=1; i<=n; i++)
{ if (x+v[i]>v[i])
{ x+=v[i];
p[i]=p[i-1];
} else
{ x=v[i];
p[i]=i;
}
if (x>max)
{ max=x;
poz=p[i];
l=i-p[i]+1;
}
}
a[n+1]=-lmx;
for (i=n; i>1; i--)
{ b[n]=1;
if (a[i+1]+v[i]>=v[i])
{ a[i]=a[i+1]+v[i];
b[i]=b[i+1];
} else a[i]=v[i];
}
for (i=n; i>1; i--)
if (a[i]<=a[i+1])
{ a[i]=a[i+1];
p[i]=p[i+1];
b[i]=b[i+1];
} else p[i]=i;
x=a[2];
a[1]=a[2];
b[1]=1;
for (i=1; i<n; i++)
{ x+=v[i];
x-=a[i]-a[i+1];
if ((x>max)&(b[i]==1))
{ max=x;
poz=p[i+1];
l=i+n-p[i+1]+1;
}
}
printf("%ld %ld %ld",max,poz,l);
}