Pagini recente » Cod sursa (job #671950) | Cod sursa (job #939774) | Cod sursa (job #2296778) | Cod sursa (job #1955373) | Cod sursa (job #333115)
Cod sursa(job #333115)
#include<stdio.h>
#define N 200010
long long n;
long long smax=-30000,pmax,lmax;
long long v[N<<1];
long long d[N<<1],st=1,dr=1;
void citire()
{
scanf("%lld",&n);
int c;
long long x;
for(long long i=1; i<=n; i++)
{
scanf("%lld%d",&x,&c);
if(c)
v[i]=x;
else
v[i]=-x;
v[i]+=v[i-1];
}
long long n1=n<<1;
for(long long i=n+1; i<=n1; ++i)
v[i]=v[i-1]+v[i-n]-v[i-n-1];
}
void rezolva()
{
long long n1=n<<1;
long long s=0,p=1,l=0;
for(int i=1; i<=n1; ++i)
{
while(st<=dr && i-d[st]>n)
++st;
while(st<dr && v[d[dr]]>v[i])
--dr;
d[++dr]=i;
s=v[i]-v[d[st]];
p=d[st]+1 <=n ? d[st]+1 : d[st]+1-n;
l=i-d[st];
if(s>smax)
{
smax=s;
pmax=p;
lmax=l;
}
else
if(s==smax)
{
if(pmax>p)
{
pmax=p;
lmax=l;
}
else
if(pmax==p)
{
if(lmax>l)
lmax=l;
}
}
}
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
pmax=1<<30;
smax=-pmax;
citire();
rezolva();
//if(lmax==n)
// printf("%d 1 %d\n",smax,n);
//else
printf("%lld %lld %lld\n",smax,pmax,lmax);
return 0;
}