Pagini recente » Cod sursa (job #450677) | Cod sursa (job #75103) | Cod sursa (job #909238) | Cod sursa (job #1068240) | Cod sursa (job #26195)
Cod sursa(job #26195)
#include <stdio.h>
#define maxn 400010
#define maxv -10000
int n,s,p;
short a[maxn];
int sum[maxn],smax[maxn],ind[maxn];
int sol,pos,l;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d ",&n);
int i,semn;
for (i=1;i<=n;i++)
{
scanf("%d %d ",&a[i],&semn);
if (!semn) a[i]=-a[i];
}
for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
for (i=1;i<=n;i++)
if (smax[i-1]>sum[i])
{
smax[i]=smax[i-1];
ind[i]=ind[i-1];
}
else {
smax[i]=sum[i];
ind[i]=i;
}
for (i=1;i<=n;i++)
{
if (s<=0)
{
s=0;
p=i;
}
s+=a[i];
if (s>sol)
{
sol=s;
pos=p;
l=i-p+1;
}
}
for (i=1;i<=n;i++)
if (sum[n]-sum[i-1]+smax[i-1]>sol)
{
sol=sum[n]-sum[i-1]+smax[i-1];
pos=i;
l=n+ind[i-1]-i+1;
}
printf("%d %d %d\n",sol,pos,l);
return 0;
}