Pagini recente » Cod sursa (job #2597766) | Cod sursa (job #608921) | Cod sursa (job #1995090) | Autentificare | Cod sursa (job #215749)
Cod sursa(job #215749)
#include<stdio.h>
#define N 400070
#define inf -1500000000
int v[N],lung,n,p,t[N],sum[N],nr[N],smax=inf;
void citire()
{
int i,x;
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d%d",&v[i],&x);
v[i+n]=v[i];
if (x==0){
v[i]=-v[i];
v[i+n]=v[i];
}
}
}
void init()
{
t[1]=0;
nr[1]=0;
for (int i=1;i<=n;i++){
sum[i]=v[i]+sum[i-1];
if (t[i-1]>sum[i-1]){
nr[i]=nr[i-1];
t[i]=t[i-1];
}
else{
nr[i]=i-1;
t[i]=sum[i-1];
}
}
}
void suma1()
{
int sc=0;
for (int i=1;i<=n;++i){
sc=t[i]+sum[n]-sum[i-1];
if (t[i]+sum[n]-sum[i-1]>smax){
smax=sc;
p=i;
lung=n-i+1+nr[i];
}
}
}
void suma2()
{
int sc=0,pp=1;
for (int i=1;i<=n;++i)
{
sc=sc+v[i];
if (sc>smax){
smax=sc;
p=pp;
lung=i-p+1;
}
if (sc<=0){
sc=0;
pp=i+1;
}
}
}
void calcul()
{
init();
suma1();
suma2();
printf("%d %d %d\n",smax , p, lung);
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
citire();
calcul();
return 0;
}