Pagini recente » Cod sursa (job #2529759) | Cod sursa (job #775205) | Cod sursa (job #2781410) | Cod sursa (job #923133) | Cod sursa (job #1100163)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int Nmax = 400100;
const int oo = 0x3f3f3f3f;
int N, V[Nmax / 2], S[Nmax], sol;
deque <int> D;
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
int tip;
fin >> V[i] >> tip;
if(!tip) V[i] = -V[i];
S[i] = S[i - 1] + V[i];
}
for(int i = N + 1; i <= N + N; i++)
S[i] = S[i - 1] + V[i - N];
sol = S[1];
D.push_back(1);
int st = 1, lg = 1;
for(int i = 2; i <= N + N; i++)
{
if(sol < S[i] - S[D.front()])
{
sol = S[i] - S[D.front()];
st = D.front() + 1;
lg = i - st + 1;
}
while(!D.empty() && S[D.back()] >= S[i])
D.pop_back();
D.push_back(i);
if(D.front() <= i - N)
D.pop_front();
}
fout << sol <<' ' << st << ' ' << lg;
return 0;
}