Pagini recente » Cod sursa (job #50534) | Cod sursa (job #1950669) | Cod sursa (job #2348550) | Cod sursa (job #1219378) | Cod sursa (job #525350)
Cod sursa(job #525350)
#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[200002],t[200002],x[200002],v[200002];
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;
}