Pagini recente » Cod sursa (job #3040472) | Cod sursa (job #2875216) | Cod sursa (job #2834072) | Cod sursa (job #2924863) | Cod sursa (job #671438)
Cod sursa(job #671438)
# include <fstream>
using namespace std;
ifstream f ("buline.in");
ofstream g ("buline.out");
int a[200005],best[200005],l[200005],l2[200005],s1[200005],s2[200005];
int lg,maxim,p,n,i,x,s,max2,poz;
int main ()
{
f>>n;
for (i=1;i<=n;i++)
{
f>>a[i];
f>>x;
if(x==0)
a[i]=-a[i];
}
best[1]=a[1];
l[1]=1;
for(i=2;i<=n;i++)
if(best[i-1]+a[i]>a[i])
{
best[i]=best[i-1]+a[i];
l[i]=l[i-1]+1;
}
else
{
best[i]=a[i];
l[i]=1;
}
maxim=-2000000000;
for(i=1;i<=n;i++)
if(best[i]>maxim)
{
maxim=best[i];
p=i-l[i]+1;
lg=l[i];
}
s=0;
max2=-2000000000;
for(i=1;i<=n;i++)
{
s+=a[i];
if (max2<s)
{
max2=s;
l[i]=i;
}
else
l[i]=l[i-1];
s1[i]=max2;
}
s=0;
max2=-2000000000;
for(i=n;i>=1;i--)
{
s+=a[i];
if (max2<s)
{
max2=s;
l2[i]=i;
}
else
l2[i]=l2[i+1];
s2[i]=max2;
}
for (i=2;i<=n;i++)
if (s2[i]+s1[i-1]>maxim)
{
maxim=s2[i]+s1[i-1];
p=l2[i];
lg=(n-l2[i]+1)+l[i-1];
}
g<<maxim<<" "<<p<<" "<<lg;
return 0;
}