Pagini recente » Cod sursa (job #2348634) | Istoria paginii runda/simulare_oji_clasa_x/clasament | Cod sursa (job #1783927) | Cod sursa (job #2153166) | Cod sursa (job #213529)
Cod sursa(job #213529)
#include<stdio.h>
#define N 200005
#define MIN -2000000
int v[N],s[N],p,lung,n,max=MIN,nr[N],t[N]={MIN};
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)
{
max=sc;
p=poz;
lung=i-poz+1;
}
if (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];
}
circular();
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
citire();
liniar();
printf("%d %d %d\n",max,p,lung);
return 0;
}