Pagini recente » Cod sursa (job #602196) | Cod sursa (job #1256223) | Cod sursa (job #1610011) | Cod sursa (job #1738740) | Cod sursa (job #71153)
Cod sursa(job #71153)
#include<stdio.h>
#define N 200001
int v[N],n,s[N],t[N],pozitie,lungime;
struct vec{
int m,lg;
}vf[N];
void read()
{
int i,nrb,color;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&nrb,&color);
if(color==0)
v[i]=-nrb;
else
v[i]=nrb;
}
}
void afis(int a[N])
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
int max(int a,int b)
{
if(a>b)
return a;
return b;
}
int v_max(vec v[N])
{
int i,maxim;
maxim=v[1].m;
for(i=1;i<n;i++)
if(v[i].m>maxim)
{
maxim=v[i].m;
lungime=v[i].lg;
pozitie=i+1;
}
return maxim;
}
void solve()
{
int i,s_max;
s[0]=v[0];
for(i=1;i<n;i++)
s[i]=s[i-1]+v[i];
//afis(v);
//afis(s);
t[0]=s[0];
for(i=1;i<n;i++)
t[i]=max(s[i-1],s[i]);
//afis(t);
for(i=1;i<n;i++)
{
vf[i].m=t[i-1]+s[n-1]-s[i-1];
vf[i].lg=i-1+n-1-(i-1);
}
//afis(vf);
s_max=v_max(vf);
printf("%d %d %d\n",s_max,pozitie,lungime);
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
read();
solve();
return 0;
}