Pagini recente » Cod sursa (job #919031) | Cod sursa (job #680767) | Cod sursa (job #2288790) | Cod sursa (job #1006384) | Cod sursa (job #839116)
Cod sursa(job #839116)
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,x,s,v[400010],t[200010],poz1,L,p2,p3,pl,DM[200010],Dm[200010],l,p1,back,back1,front,front1;
int main ()
{
f>>n;
int max=-1<<15;
for(i=1;i<=n;++i)
{
f>>t[i]>>s;
v[i]=v[i-1];
if(!s)
t[i]=-t[i];
v[i]+=t[i];
if(t[i]>max)
{
max=t[i];
p2=i-1;
L=2;
}
}
for(i=n+1;i<=2*n;++i)
{
v[i]=v[i-1]+t[i%n];
}
front=1; back=0;
front1=1; back1=0;
++n;
for(i=0;i<=2*n-2;++i)
{
while(front<=back&&v[i]<=v[Dm[back]]) --back;
Dm[++back]=i;
if(Dm[front]==i-n)
++front;
if(v[i]-v[Dm[front]]>max)
{
max=v[i]-v[Dm[front]];
p1=i; p2=Dm[front];
L=p1-p2+1;
if(L<0)
L+=n;
}
}
g<<max<<" "<<p2+1<<" "<<L-1;
return 0;
}