Pagini recente » Cod sursa (job #901223) | Cod sursa (job #799302) | Cod sursa (job #2590993) | Cod sursa (job #1254436) | Cod sursa (job #429924)
Cod sursa(job #429924)
#include <stdio.h>
FILE *f=fopen("buline.in","r"),*g=fopen("buline.out","w");
int i,n,v[400001],p,l,pm,lm,sm=-2000000000,t,s[400001],j,max[400001],poz[400001],max2[400001],poz2[400001];
int main(void)
{
fscanf(f,"%d",&n);
for (i=1;i<=n;i++)
{
fscanf(f,"%d%d",&v[i],&t);
if (t==0)
v[i]=v[i]*(-1);
s[i]=s[i-1]+v[i];
if (s[i]-max[i-1]>sm)
{
sm=s[i]-max[i-1];
pm=poz[i-1]+1;
lm=i-poz[i-1];
}
if (s[i]<max[i-1])
{
max[i]=s[i];
poz[i]=i;
}
else
{
max[i]=max[i-1];
poz[i]=poz[i-1];
}
}
max2[n]=s[n];
poz2[n]=n;
for (i=n-1;i>0;i--)
{
if (max2[i+1]>s[i])
{
max2[i]=s[i];
poz2[i]=i;
}
else{
max2[i]=max2[i+1];
poz2[i]=poz2[i+1];
}
}
for (i=1;i<=n;i++)
{
s[i+n]=s[i+n-1]+v[i];
if (s[i+n]-max2[i]>sm)
{
sm=s[i+n]-max2[i];
pm=poz2[i]+1;
lm=i+n-poz2[i];
}
}
fprintf(g,"%d %d %d\n",sm,pm,lm);
fclose(g);
return 0;
}