Pagini recente » Diferente pentru problema/smen intre reviziile 8 si 7 | Cod sursa (job #1145716) | Cod sursa (job #996135) | Cod sursa (job #2580525) | Cod sursa (job #1913391)
#include<bits/stdc++.h>
#define maxN 200005
using namespace std;
int n,st,dr,v[maxN],c;
long long s[maxN],sol=-LLONG_MAX;
int m[maxN];
deque<int> q;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&c);
if(!c) v[i]=-v[i];
v[n+i]=v[i];
}
for(int i=1;i<=(2*n);i++) s[i]=s[i-1]+1LL*v[i];
//m[i]-indicele minimului dintre [s[1],s[i]]
m[0]=0;
for(int i=1;i<=n;i++)
{
if(s[m[i-1]]<=s[i])
{
m[i]=m[i-1];
}
else m[i]=i;
}
for(int i=1;i<=(2*n);i++)
{
while(!q.empty() && s[q.back()]>=s[i])
{
q.pop_back();
}
q.push_back(i);
while(q.front()<=(i-n)) q.pop_front();
if(i>n)
{
m[i]=q.front();
}
}
for(int i=1;i<=2*n;i++)
{
if((s[i]-s[m[i-1]])>sol)
{
sol=s[i]-s[m[i-1]];
st=m[i-1]+1;
dr=i;
}
}
printf("%lld %d %d\n",sol,st,dr-st+1);
return 0;
}