Pagini recente » Cod sursa (job #1885953) | Cod sursa (job #1650743) | Cod sursa (job #1172569) | Cod sursa (job #374543) | Cod sursa (job #813469)
Cod sursa(job #813469)
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,x,s,v[200010],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];
}
for(i=n+1;i<=2*n;++i)
{
v[i]=v[i-1]+t[i%n];
}
front=1; back=0;
front1=1; back1=0;
for(i=1;i<=2*n;++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]+l-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;
}