Pagini recente » Cod sursa (job #314953) | Cod sursa (job #2361193) | Cod sursa (job #3233004) | Cod sursa (job #2441584) | Cod sursa (job #257194)
Cod sursa(job #257194)
#include<stdio.h>
#define N 200001
int n,i,s,s1,s2,l1,l2,S,P,L,a[N],b[N],c[N],d[N],e[N],f[N],g[N];
void readd(),prelucrari(),solve();
int main()
{
readd();
prelucrari();
solve();
return 0;
}
void readd()
{
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);a[i]=(s)?a[i]:-a[i];
}
}
void prelucrari()
{
for(i=1;i<=n;i++)b[i]=b[i-1]+a[i];
for(i=n;i>=1;i--)c[i]=c[i+1]+a[i];
d[1]=b[1];e[1]=1;
for(i=2;i<=n;i++)
{
d[i]=d[i-1];e[i]=e[i-1];
if(b[i]>d[i]){d[i]=b[i];e[i]=i;}
}
f[n]=c[n];g[n]=n;
for(i=n-1;i>=1;i--)
{
f[i]=f[i+1];g[i]=g[i+1];
if(c[i]<=f[i]){f[i]=c[i];g[i]=i;}
}
}
void solve()
{
for(i=1;i<=n;i++)
{
s1=c[i]+d[i-1];
l1=n-i+1+e[i-1];
s2=c[i];
l2=n-i+1;
if(s2>=s1){s1=s2;l1=l2;}
s2=c[i]-f[i];
l2=g[i+1]-i+1;
if(s2>=s1){s1=s2;l1=l2;}
if(s1>S){S=s1;P=i;L=l1;}
}
printf("%d %d %d",S,P,L);
}