Pagini recente » Cod sursa (job #1478315) | Cod sursa (job #3194257) | Cod sursa (job #1521761) | Cod sursa (job #2480186) | Cod sursa (job #3264327)
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>
#define int long long
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int MAX=2e5;
int n,i,v[2*MAX+5],sol=INT_MIN,poz=INT_MAX,lmin=INT_MAX,val,sp[2*MAX+5],lungime,ind;
deque <int> dq;
signed main()
{
fin>>n;
for (i=1; i<=n; i++)
{
fin>>v[i]>>val;
if (val==0)
v[i]=-v[i];
}
for (i=n+1; i<=2*n; i++)
v[i]=v[i-n];
for (i=1; i<=2*n; i++)
sp[i]=sp[i-1]+v[i];
for (i=1; i<=2*n; i++)
{
if (dq.front()==i-n-1)
dq.pop_front();
while (!dq.empty() && sp[dq.back()]>sp[i-1])
dq.pop_back();
dq.push_back(i-1);
ind=dq.front()+1;
lungime=i-ind+1;
val=sp[i]-sp[ind-1];
if (val>sol)
{
sol=val;
poz=ind;
lmin=lungime;
}
else
{
if (val==sol)
{
if (ind<poz)
{
poz=ind;
lmin=lungime;
}
else if (ind==poz)
{
if (lungime<lmin)
lmin=lungime;
}
}
}
}
fout<<sol<<" "<<poz<<" "<<lmin;
return 0;
}