Pagini recente » Cod sursa (job #1164774) | Cod sursa (job #592290) | Cod sursa (job #1469567) | Cod sursa (job #2289464) | Cod sursa (job #25835)
Cod sursa(job #25835)
#include <stdio.h>
int v[200001],
s[2][200001],
e[2][200001];
int i,a,b,n;
void solve()
{
int sum_m,sum_c,p_i,in,sf,i,x,y,q,part,poz=0,max;
sum_m=v[1];
sum_c=sum_m;
p_i=1;
in=1;
sf=1;
for (i=2;i<=n;++i)
{
if (sum_c<0)
{
sum_c=v[i];
p_i=i;
} else sum_c+=v[i];
if (sum_c>sum_m)
{
sum_m=sum_c;
in=p_i;
sf=i;
}
}
max=0;
part=0;
poz=0;
for (i=1;i<=n;++i)
{
part+=v[i];
if (max<part)
{
max=part;
poz=i;
}
s[0][i]=max;
e[0][i]=poz;
}
max=0;
part=0;
poz=0;
for (i=n;i>0;--i)
{
part+=v[i];
if (max<part)
{
max=part;
poz=i;
}
s[1][i]=max;
e[1][i]=poz;
}
//q=-1;
for (i=1;i<=n-1;++i)
if (sum_m<s[0][i]+s[1][i+1])
{
sum_m=s[0][i]+s[1][i+1];
in=e[1][i];
sf=e[0][i];
}
/*else if (sum_m==(s[0][i]+s[1][i+1]))
{*/
if (in>sf) printf("%d %d %d\n",sum_m,in,n-in+1+sf); else printf("%d %d %d\n",sum_m,in,sf-in+1);
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d %d",&a,&b);
if (b>0) v[i]=a; else v[i]=-1*a;
}
solve();
return 0;
}