Pagini recente » Cod sursa (job #1622417) | Cod sursa (job #1466751) | Cod sursa (job #2461251) | Cod sursa (job #1173287) | Cod sursa (job #75441)
Cod sursa(job #75441)
#include<stdio.h>
#define N 200001
int v[N],n,s[N],t[N],vf[N],poz,lg,s_max;
void read()
{
int i,nrb,color;
scanf("%d",&n);
for(i=1;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=1;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(int v[N])
{
int i,max;
max=v[1];
for(i=1;i<=n;i++)
if(v[i]>max)
{
max=v[i];
poz=i;
}
return max;
}
int mul(int vf[N])
{
int nr=0,i;
for(i=1;i<=n;i++)
if(vf[i]==s_max)
nr++;
if(nr>1)
return 1;
return 0;
}
int lungime(int poz)
{
int nr,sum;
sum=v[poz];
nr=0;
while(sum!=s_max)
{
poz++;
if(poz==n+1)
poz=0;
sum+=v[poz];
nr++;
}
return nr;
}
void solve()
{
int i,poz_f,nr,max2,max3;
s[1]=v[1];
for(i=2;i<=n;i++)
s[i]=s[i-1]+v[i];
//afis(v);
//afis(s);
t[1]=s[1];
for(i=2;i<=n;i++)
t[i]=max(t[i-1],s[i]);
//afis(t);
for(i=1;i<=n;i++)
vf[i]=t[i-1]+s[n]-s[i-1];
//afis(vf);
s_max=v_max(vf);
poz_f=poz;
nr=lungime(poz);
max2=max3=1000000000;
if(!mul(vf))
{
printf("%d %d %d\n",s_max,poz_f,nr);
return;
}
else
{
for(i=1;i<=n;i++)
if(vf[i]==s_max&&i<max3&&lungime(i)<max2)
{
poz_f=i;
max2=lungime(i);
}
printf("%d %d %d\n",s_max,poz_f,max2);
}
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
read();
if(n==1)
{
printf("1 1 1\n");
return 0;
}
solve();
return 0;
}