Pagini recente » Cod sursa (job #3320632) | Cod sursa (job #3344900) | Cod sursa (job #3328130) | Cod sursa (job #3310997) | Cod sursa (job #3346560)
#include <fstream>
#include <deque>
#define NMAX 200005
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int N;
long long v[2*NMAX], sp[2*NMAX];
int main()
{
fin >> N;
int x,c;
for(int i=1;i<=N;i++)
{
fin>>x>>c;
if(c==0) v[i] = -x;
else v[i] = x;
v[i+N] = v[i];
}
for(int i=1;i<=2*N;i++)
sp[i] = sp[i-1] + v[i];
deque<int> dq;
dq.push_back(0);
long long Smax = -9e18;
int P=1,L=1;
for(int i=1;i<=2*N;i++)
{
while(!dq.empty() && dq.front() < i-N)
dq.pop_front();
long long s = sp[i] - sp[dq.front()];
int start = dq.front()+1;
int len = i - dq.front();
int realP = (start-1)%N + 1;
if(s > Smax)
{
Smax = s;
P = realP;
L = len;
}
while(!dq.empty() && sp[dq.back()] >= sp[i])
dq.pop_back();
dq.push_back(i);
}
fout<<Smax<<" "<<P<<" "<<L;
}