Pagini recente » Cod sursa (job #1763214) | Cod sursa (job #1291924) | Cod sursa (job #976592) | Cod sursa (job #1451738) | Cod sursa (job #430417)
Cod sursa(job #430417)
#include<stdio.h>
int x[400001], d[400001],n,i,a,b,p,u,max,q,q1;
FILE *f,*g;
int main(){
f=fopen("buline.in","r");
g=fopen("buline.out","w");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
fscanf(f,"%d%d",&a,&b);
if(b==0)
x[i]=-a;
else
x[i]=a;
x[n+i]=x[i];
}
for(i=1;i<=2*n;i++)
x[i]=x[i-1]+x[i];
p=u=1;
d[p]=0;
for(i=1;i<=2*n;i++)
{
while(i-d[p]>n&&p<=u)
p++;
while(x[i]-x[d[p]]<=x[d[u]]&&u>=p)
u--;
u++;
d[u]=i;
if(x[i]-x[d[p]]>max){
max=x[i]-x[d[p]];
if(i<=n){
q=d[p]+1;
q1=i;}
else{
q=i-n;
q1=i-d[p];
}
}
}
fprintf(g,"%d %d %d",max,q,q1);
return 0;
}