Pagini recente » Cod sursa (job #2915824) | Cod sursa (job #2366938) | Cod sursa (job #412117) | Cod sursa (job #992999) | Cod sursa (job #795268)
Cod sursa(job #795268)
#include<fstream>
#define dim 400002
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int v[dim],n,x,o,i,end,deque[dim],begin,idx,front,back;
long long Max,S[dim];
int main () {
f>>n;
for(i=1;i<=n;++i){
f>>x>>o;
if(o==0)
x=-x;
v[i+n]=v[i]=x;
}
for(i=1;i<=2*n ;++i){
S[i]=S[i-1]+v[i];
}
front=1;back=0;
begin=1;
end=n;
Max=S[n];
for(i=1;i<=2*n;++i){
while (front<=back && deque[front]<i-n)
++front;
if(Max<S[i]-S[deque[front]]){
Max=S[i]-S[deque[front]];
begin=deque[front]+1;
end=i;
}
while(front<=back && S[deque[back]]>S[i] )
--back;
deque[++back]=i;
}
g<<Max<<" "<<begin<<" "<<end-begin+1<<"\n";
return 0;
}