Pagini recente » Cod sursa (job #1770057) | Cod sursa (job #2059550) | Cod sursa (job #1822809) | Cod sursa (job #1984052) | Cod sursa (job #29760)
Cod sursa(job #29760)
#include <stdio.h>
#include <stdlib.h>
#define nmax 200000
int b[nmax],k,lmax,pmax,p;
long n,i,s,sum[nmax],best[nmax],max;
int main()
{
freopen("buline.in","r",stdin);
scanf("%ld\n",&n);
for (i=0;i<n;++i)
{
scanf("%d %d\n",&b[i],&k);
if (k==0) b[i]*=-1;
}
fclose(stdin);
p=0;
s=b[0];
max=s;
pmax=1;
lmax=1;
sum[0]=b[0];
best[0]=0;
for (i=1;i<n;++i)
{
sum[i]=sum[i-1]+b[i];
if (sum[i]>sum[best[i-1]]) best[i]=i;
else best[i]=best[i-1];
if (s+b[i]>b[i]) s+=b[i];
else {
s=b[i];
p=i;
}
if (s>max)
{
max=s;
pmax=p;
lmax=i-p+1;
}
}
--n;
for (i=0;i<n;++i)
{
if ((sum[best[i]]+sum[n]-sum[i]>max)||((sum[best[i]]+sum[n]-sum[i]==max)&&(i<pmax))||((sum[best[i]]+sum[n]-sum[i]==max)&&(i==pmax)&&(n-i+best[i]<lmax)))
{
max=sum[best[i]]+sum[n]-sum[i];
pmax=i+1;
lmax=n-i+best[i]+1;
}
}
freopen("buline.out","w",stdout);
printf("%ld %d %d",max,pmax+1,lmax);
return 0;
}