Pagini recente » Cod sursa (job #1072506) | Cod sursa (job #2813132) | Cod sursa (job #2497471) | Cod sursa (job #3151723) | Cod sursa (job #526375)
Cod sursa(job #526375)
#include<stdio.h> //p=??? l=???
int modul(int x)
{
if(x<0)
return -x;
return x;
}
int n,S,Smax,l,p,Lmin=10000000,Pmin=10000000,nr,ok,end;
int sume[400002],t[400002],x[400002],v[400002];
int main()
{
int i;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&nr,&ok);
if(ok==0)
v[i]=-nr;
if(ok==1)
v[i]=nr;
}
for(i=1;i<=n-1;i++)
v[n+i]=v[i];
sume[1]=v[1];
for(i=2;i<=2*n-1;i++)
sume[i]=sume[i-1]+v[i];
//////////////////////////////////////////////////////////
Smax=-2000000000;
int first = 1, last = 1;
x[1]=sume[1];
t[1] = 1;
for(i=2;i<=2*n-1 ;i++)
{
while(sume[i] > x[last] && last >= first)
last--;
x[ ++last ] = sume[ i ];
t[ last ] = i;
if( t[ first ] + n <= i ) first++;
if(i < n) continue;
S= x[first]-sume[ i - n ];
end=t[first];
p=i-n+1;
l=modul(end-p)+1;
if(S>Smax && i >= n)
{
Smax=S;
Lmin=l;
Pmin=p;
}
if(S==Smax && i>=n)
{
if(p<Pmin)
Pmin=p;
else
if(l<Lmin)
Lmin=l;
}
}
////////////////////////////////////
for(i=2*n;last>=first;i++)
{
if( t[ first ] + n <= i ) first++;
if(first > last) break;
S= x[first]-sume[ i - n ];
end=t[first];
p=i-n+1;
l=modul(end-p)+1;
if(S>Smax && i >= n)
{
Smax=S;
Lmin=l;
Pmin=p;
}
if(S==Smax && i>=n)
{
if(p<Pmin)
Pmin=p;
else
if(l<Lmin)
Lmin=l;
}
}
printf("%d %d %d\n",Smax,Pmin,Lmin);
return 0;
}