Pagini recente » Cod sursa (job #3203808) | Cod sursa (job #2868844) | Cod sursa (job #2840045) | Cod sursa (job #1143044) | Cod sursa (job #3165092)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int ok,i,n,v[400001],st,dr;
long long sum,maxim=-4000000001,s[400001];
deque <int> d;
int main ()
{
fin>>n;
for (i=1; i<=n; i++)
{
fin>>v[i]>>ok;
if (ok==0)
v[i]=-v[i];
s[i]=s[i-1]+v[i];
}
for (i=n+1; i<=2*n; i++)
{
v[i]=v[i-n];
s[i]=s[i-1]+v[i];
}
d.push_back (0);
for (i=1; i<=2*n; i++)
{
sum=s[i]-s[d.front ()];
if (sum>maxim)
{
maxim=sum;
st=d.front ()+1;
dr=i;
}
while (!d.empty ()&&s[i]<=s[d.back ()])
d.pop_back ();
d.push_back (i);
if (i>=n)
{
if (d.front ()==i-n)
d.pop_front ();
}
}
fout<<maxim<<" "<<st<<" "<<dr-st+1;
return 0;
}