Pagini recente » Cod sursa (job #1155292) | Cod sursa (job #722407) | Cod sursa (job #925615) | Cod sursa (job #3213182) | Cod sursa (job #353851)
Cod sursa(job #353851)
#include<iostream>
#include<string>
using namespace std;
#define nm 200005
#define inf 1000000001
int a[nm],sum[nm],best[nm],lb[nm];
inline int rs(int a,int b)
{
return sum[b]-sum[a-1];
}
int main()
{
int n,s,i,ans=-inf,anss,ansl;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d %d",&a[i],&s);
if(!s) a[i]*=(-1);
sum[i]=sum[i-1]+a[i];
}
for(i=n;i>=1;--i)
if(best[i+1]>=rs(i,n))
{
best[i]=best[i+1];
lb[i]=lb[i+1];
}
else
{
best[i]=rs(i,n);
lb[i]=n-i+1;
}
int sump=-inf,l=0;
for(i=1;i<=n;++i)
{
if(sump+a[i]>a[i])
{
sump+=a[i];
++l;
}
else
{
sump=a[i];
l=1;
}
if(sump>ans)
{
ans=sump;
anss=i-l+1;
ansl=l;
}
else if(sump==ans) if(i-l+1<anss)
{
anss=i-l+1;
ansl=l;
}
else if(i-l+1==anss) if(l<ansl) ansl=l;
int as=sum[i]+best[i+1],ass=n-lb[i+1]+1,asl=i+lb[i+1];
if(as>ans)
{
ans=as;
anss=ass;
ansl=asl;
}
else if(as==ans) if(ass<anss)
{
anss=ass;
ansl=asl;
}
else if(ass==anss) if(asl<ansl) ansl=asl;
}
printf("%d %d %d",ans,anss,ansl);
return 0;
}