Pagini recente » Cod sursa (job #3179902) | Cod sursa (job #381411) | Cod sursa (job #1480711) | Cod sursa (job #576282) | Cod sursa (job #36910)
Cod sursa(job #36910)
#include <stdio.h>
#define INF "buline.in"
#define OUF "buline.out"
#define NMAX 262144
#define MAX(a,b) ((a>b)?(a):(b))
int a[NMAX],s[NMAX],best[NMAX],end[NMAX],n;
int main()
{
FILE *in,*out;
register int i,x,bsecv,secv,p,q;
in=fopen(INF,"r");
out=fopen(OUF,"w");
fscanf(in,"%d",&n);
s[0]=0;best[0]=0;p=q=0;bsecv=secv=(1<<30)*(-1);
for(i=1;i<=n;i++)
{
fscanf(in,"%d %d",a+i,&x);
if(!x) a[i]*=(-1);
s[i]=s[i-1]+a[i];
if(secv+a[i]>a[i])
{
secv+=a[i];
best[i]=best[i-1];
}
else
{
secv=a[i];
best[i]=i;
}
if(secv>bsecv) { bsecv=secv;p=best[i];q=i-p+1; }
}
best[0]=(1<<30)*(-1);end[0]=0;
for(i=1;i<=n;i++)
if(s[i]>best[i-1])
{
best[i]=s[i];
end[i]=i;
}
else
{
best[i]=best[i-1];
end[i]=end[i-1];
}
for(i=1;i<=n;i++)
if(s[n]-s[i-1]+best[i-1]>bsecv)
{
bsecv=s[n]-s[i-1]+best[i-1];
p=i;q=n-i+1+end[i-1];
}
fprintf(out,"%d %d %d",bsecv,p,q);
fclose(in);fclose(out);
return 0;
}