Pagini recente » Cod sursa (job #1760972) | Cod sursa (job #814936) | Cod sursa (job #264986) | Cod sursa (job #195789) | Cod sursa (job #26766)
Cod sursa(job #26766)
#include<stdio.h>
#define infi 10005
#define nmax 200000
int long max=-infi,s[nmax],n,inc,sf,lung;
void afiseaza();
void citeste()
{int long i,a,b;
freopen("buline.in","r",stdin);
scanf("%ld",&n);
for(i=1;i<=n;i++)
{scanf("%ld%ld",&a,&b);
if(!b)
s[i]=-a;
else
s[i]=a;
}
}
int long caz_1()
{int long i,j,in,coada=0;
for(i=1;i<=n;i++)
{coada+=s[i-1];
if(coada<=0)
{coada=0;in=i;}
if(coada+s[i]>max)
{max=coada+s[i];
inc=in;
sf=i;
lung=sf-inc+1;
}
}
}
void caz_2()
{int long i,sff[nmax],incc[nmax],s1[nmax],s2[nmax],ma1[nmax],ma2[nmax];
for(i=0;i<=n+1;i++)
ma1[i]=ma2[i]=-infi;
s2[n+1]=s1[0]=0;
for(i=1;i<=n;i++)
{s1[i]=s1[i-1]+s[i];
if(s1[i]>ma1[i-1])
{ma1[i]=s1[i];
sff[i]=i;
}
else
{ma1[i]=ma1[i-1];
sff[i]=sff[i-1];
}
}
for(i=n;i>=1;i--)
{s2[i]=s2[i+1]+s[i];
if(s2[i]>ma2[i+1])
{ma2[i]=s2[i];
incc[i]=i;
}
else
{ma2[i]=ma2[i+1];
incc[i]=incc[i+1];
}
}
for(i=1;i<n-1;i++)
if(ma1[i]+ma2[i+2]>max)
{max=ma1[i]+ma2[n-i-1];
inc=incc[n-i-1];
sf=sff[i];
lung=sf+n-inc+1;
}
}
int main()
{citeste();
//caz_1();
caz_2();
afiseaza();
return 0;
}
void afiseaza()
{freopen("buline.out","w",stdout);
printf("%ld %ld %ld",max,inc,lung);
fclose(stdout);
}