Pagini recente » Cod sursa (job #2791827) | Cod sursa (job #342405)
Cod sursa(job #342405)
#include<cstdio>
#define N 200001
int n,s,maxim=-N,lung,p,poz;
struct {short int val;int s;}v[N];
void circ()
{
int cn=2*n;
int max1=-N,pozm,sum;
for (int i=n+2; i<cn;++i)
{
if (max1<v[i-n-1].s)
{
max1=v[i-n-1].s;
pozm=i-n-1;
}
sum=v[n].s-v[i-n-1].s+max1;
if (maxim<sum)
{
maxim=sum;
poz=i-n;
lung=n-i+n+1+pozm;
continue;
}
if (sum==maxim)
{
if (pozm==poz)
if (lung>n-i+n+1+pozm)
lung=n-i+n+1+pozm;
else
if (poz>pozm)
{
poz=i-n;
lung=n-i+n+1+pozm;
}
}
}
}
void citire()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
int x;
short int y;
for (int i=1; i<=n; ++i)
{
scanf("%d%hd",&x,&y);
if (y)
v[i].val=x;
else
v[i].val=x*(-1);
v[i].s=v[i-1].s+v[i].val;
s+=v[i].val;
if (s>maxim)
{
maxim=s;
poz=p+1;
lung=i-p;
}
if (s<0)
{
s=0;
p=i;
}
}
circ();
printf("%d %d %d",maxim,poz,lung);
}
int main()
{
citire();
return 0;
}