Pagini recente » Cod sursa (job #760570) | Cod sursa (job #495574) | Cod sursa (job #1175524) | Cod sursa (job #1501217) | Cod sursa (job #222413)
Cod sursa(job #222413)
#include<stdio.h>
long long nr[400100],sum[400100];
struct xx{
long long v,p;
}t[400100];
int main(){
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
long long n,i,a,b,maxim,pmin,lung,s;
scanf("%lld",&n);
t[0].v=-1000000;
for(i=1;i<=n;++i){
scanf("%lld%lld",&a,&b);
if(b)
nr[i]=nr[n+i]=a;
else
nr[i]=nr[n+i]=-a;
}
t[0].p=1;
for(i=1;i<=n<<1;++i){
sum[i]=sum[i-1]+nr[i];
if(t[i-1].v>sum[i]){
t[i].v=t[i-1].v;
t[i].p=t[i-1].p;
}
else{
t[i].v=sum[i];
t[i].p=i;
}
}
t[0].v=0;
maxim=-10000000;
pmin=lung=0;
for(i=1;i<=2*n;++i){
s=t[i-1].v-sum[i-1]+sum[n];
if(maxim<s){
maxim=s;
pmin=i;
lung=n-(i-t[i-1].p-1);
}
}
if(pmin>n)
pmin-=n;
printf("%lld %lld %lld\n",maxim,pmin,lung);
fclose(stdin);
fclose(stdout);
return 0;
}