Pagini recente » Cod sursa (job #1246307) | Cod sursa (job #2337486) | Cod sursa (job #2429271) | Cod sursa (job #2849286) | Cod sursa (job #71163)
Cod sursa(job #71163)
#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;
s[1]=v[1];
for(i=2;i<=n;i++)
s[i]=s[i-1]+v[i];
//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=0;
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&&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();
solve();
return 0;
}