Pagini recente » Cod sursa (job #1105104) | Cod sursa (job #1483916) | Cod sursa (job #780707) | Cod sursa (job #952531) | Cod sursa (job #27671)
Cod sursa(job #27671)
#include<stdio.h>
#include<iostream.h>
#define MAXN 400001
#define INF 2000000002
long pA,pB,N,U,L;
long V[MAXN];
long poz[MAXN],query[MAXN];
long REZ, X[MAXN],m;
long deque[MAXN];
void citesteDate()
{
int i;
freopen("buline.in","r",stdin);
scanf("%d",&N);L=1;U=N;
//cout<<N<<endl;
for(i=1;i<=N;i++){
scanf("%d %d ",&V[i],&m);if(!m) V[i]=-V[i];}
for(i=N+1;i<=2*N;i++)
V[i]=V[i-N];
//for(i=1;i<=2*N;i++) printf("%d %d \n",V[i],m);
}
void proceseaza()
{
int i,j,s1,s2;
for(s1=1,s2=1,i=1;i<=2*N;i++)
{ j=i;
X[j]=X[j-1]+V[j];;
while (s1<=s2 && deque[s2]>X[j]) s2--;
s2++;
deque[s2]=X[j];
poz[s2]=j;
while (s1<=s2 && poz[s1]+U-L<j) s1++;
query[j]=poz[s1];
}
REZ=-INF; ;
for(i=L;i<=2*N;i++)
{
j=query[i-L];
if (X[i]-X[j]>REZ)
{REZ=X[i]-X[j];pA=j+1;pB=i;}
}
cout<<REZ<< ' '<<pA<<pB-pA+1<<endl;
}
void afiseazaRez()
{
freopen("buline.out","w",stdout);
//if (pB>N)pB-=N;
printf("%ld\n%d %d\n",REZ,pA,pB-pA+1);
}
int main()
{
citesteDate();
proceseaza();
afiseazaRez();
return 0;
}