Pagini recente » Cod sursa (job #680876) | Cod sursa (job #2706375) | Cod sursa (job #1970146) | Cod sursa (job #408330) | Cod sursa (job #431827)
Cod sursa(job #431827)
#include<stdio.h>
using namespace std;
FILE *f=fopen("buline.in","r");
FILE *g=fopen("buline.out","w");
int semn[2]={-1,1};
int n,i,s[400001],a[200001],x,p,u,d[400001],maxim,max_poz,max_l;
int main(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
fscanf(f,"%d",&a[i]);
fscanf(f,"%d",&x);
a[i]*=semn[x];
s[i]=s[i-1]+a[i];
}
for(i=1;i<=n;i++)
s[i+n]=s[i+n-1]+a[i];
u=1;
p=1;
d[p]=0;
for(i=1;i<=2*n;i++){
while( i-d[p] > n && p<=u )
p++;
if(p<=u){
if(s[i]-s[d[p]] > maxim ){
maxim=s[i]-s[d[p]];
max_poz=d[p]+1;
max_l=i-d[p];
}
}
while( s[d[u]] >= s[i] && u>=p )
u--;
d[++u]=i;
}
fprintf(g,"%d %d %d",maxim,max_poz,max_l);
return 0;
}