Pagini recente » Cod sursa (job #2267002) | Cod sursa (job #1954851) | Cod sursa (job #2279416) | Cod sursa (job #1387881) | Cod sursa (job #127826)
Cod sursa(job #127826)
#include<stdio.h>
#define NMAX 500001
long y[NMAX],z[NMAX],x[NMAX],a,b,i,k,l,p,poz,max,m,s,lung,n;
long maxim(long a,long b)
{
if (a>b) return a;
return b;
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld%ld",&a,&b);
if (b==0) x[i]=0-a;
else
x[i]=a;
x[n+i]=x[i];
}
/* s=x[1];
l=1;
p=1;
max=s;
lung=l;
poz=p;
m=n+n;
for (i=1;i<=m;i++)
if (l<=n)
{
if (s+x[i]<0)
{
if (s>max)
{
max=s;
poz=p;
lung=l;
}
s=x[i];
l=1;
p=i;
} else
{
if (s>max)
{
max=s;
poz=p;
lung=l;
}
s+=x[i];
l++;
}
}
/* else
{
p=p+1;
l=0;
s=0;
}
*/
s=0;
p=1;
l=0;
max=-1000000;
for (i=1;i<=n;i++)
{
if (s+x[i]<0)
{
if (s>max)
{
max=s;
poz=p;
lung=l+1;
}
p=i+1;
l=0;
s=0;
} else
{
if (s>max)
{
max=s;
poz=p;
lung=l;
}
if (s+x[i]>max)
{
s+=x[i];
max=s;
poz=p;
lung=l+1;
}
l++;
}
}
for (i=1;i<=n;i++)
y[i]=y[i-1]+x[i];
z[1]=x[1];
for (i=2;i<=n;i++)
z[i]=maxim(z[i-1],y[i]);
for (i=2;i<=n;i++)
{
s=z[i-1]+y[n]-y[i-1];
if (s>max)
{
max=s;
poz=i;
lung=-1000;
}
}
if (lung==-1000)
{
s=0;
for (i=poz;s!=max;i++)
s+=x[i];
i--;
lung=i-poz+1;
}
printf("%ld %ld %ld\n",max,poz,lung);
return 0;
}