Pagini recente » Cod sursa (job #2522913) | Cod sursa (job #475413) | Cod sursa (job #2391538) | Cod sursa (job #234839) | Cod sursa (job #214229)
Cod sursa(job #214229)
#include<stdio.h>
#define N 200005
#define MIN -2000000
int v[N],s[N],p,lung,n,max=MIN,nr[N],t[N]={MIN},min=N;
void circular()
{
int i;
for (i=2; i<=n;++i)
if (t[i-1]>=s[i-1])
{
nr[i]=nr[i-1];
t[i]=t[i-1];
}
else
{
nr[i]=i-1;
t[i]=s[i-1];
}
for (i=1; i<=n;++i)
{
if (t[i]+s[n]-s[i-1]>max)
{
max=t[i]+s[n]-s[i-1];
p=i;
lung=n-i+1+nr[i];
}
}
}
void liniar()
{
int sc=0,poz=1,i;
for (i=1; i<=n;++i)
{
sc+=v[i];
if(sc==max)
if(poz<p || poz==p && i-poz+1<lung)
{
p=poz;
lung=i-poz+1;
}
if (sc>max)
{
max=sc;
p=poz;
lung=i-poz+1;
}
if (sc<0)
{
sc=0;
poz=i;
}
}
}
void citire()
{
int a,i;
scanf("%d",&n);
for (i=1; i<=n; ++i)
{
scanf("%d%d",&v[i],&a);
if (!a)
v[i]=-v[i];
s[i]=s[i-1]+v[i];
}
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
citire();
circular();
liniar();
printf("%d %d %d\n",max,p,lung);
return 0;
}