Pagini recente » Cod sursa (job #172622) | Cod sursa (job #1600069) | Cod sursa (job #1545061) | Cod sursa (job #783705) | Cod sursa (job #669791)
Cod sursa(job #669791)
#include<iostream>
#include<fstream>
using namespace std;
int v[200001],s[400001],deque[400001];
int main ()
{
int i,n,x,y,max,start,l,st,dr,m;
ifstream f("buline.in");
ofstream g("buline.out");
f>>n;
for(i=1;i<=n;i++) {
f>>x>>y;
if(y==0)
x=x*(-1);
v[i]=x;
}
f.close();
for(i=1;i<=n;i++)
s[i]=s[i-1]+v[i];
for(i=1;i<=n;i++)
s[i+n]=s[i+n-1]+v[i];
m=n+n;
st=1;
dr=0;
max=-1;
for(i=1;i<=m;i++) {
while((st<=dr)&&(s[deque[dr]]>s[i]))
dr--;
deque[++dr]=i;
if((i-deque[st])==n)
st++;
if((s[i]-s[deque[st]])>max) {
max=s[i]-s[deque[st]];
start=deque[st]+1;
l=i-deque[st];
}
}
g<<max<<" "<<start<<" "<<l;
g.close();
return 0;
}