Pagini recente » Cod sursa (job #1498673) | Cod sursa (job #2750002) | Cod sursa (job #2555871) | Cod sursa (job #3159726) | Cod sursa (job #2099886)
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int n,i,x,sgn,v[400001],deq[400001],sum[400001],p,smax,minim,st,dr,l;
int main(){
fin>>n;
for(i=1;i<=n;i++){
fin>>x>>sgn;
if(!sgn)
x*=-1;
v[i]=x;
}
for(i=1;i<n;i++)
v[n+i]=v[i];
//sum = vector de sume partiale
//suma partiala de i este suma tuturor elementelor cu nr de ord mai mic sau egal cu i
//ca sa aflii suma dintre pozitiile a si b faci sp[a]-sp[b]
//aici faci deque ca sa aflii s.p. maxima dintre oricare 2 elemente
deq[++dr]=1;
sum[1]=v[1];
for(i=2;i<2*n;i++){
sum[i]=v[i]+sum[i-1];
minim=sum[deq[st]];
if(sum[i]-minim>smax){
smax=sum[i]-minim;
p=deq[st]+1;
l=i-p+1;
}
while(st<=dr && sum[i]<sum[deq[dr]])
--dr;
deq[++dr]=i;
if(deq[st]<i-n+1)
++st;
}
fout<<smax<<" "<<p<<" "<<l;
return 0;
}