Pagini recente » Cod sursa (job #772876) | Cod sursa (job #2379148) | Cod sursa (job #2267659) | Cod sursa (job #382816) | Cod sursa (job #1747530)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");
const int maxn = 400005;
deque <int> dq;
int sp[maxn];
int v[maxn];
int main()
{
int n;
in >> n;
for(int i = 1; i <= n; i++)
{
int aux;
in >> v[i] >> aux;
if(aux == 0)
v[i] = -v[i];
v[i + n] = v[i];
}
for(int i = 1; i <= n * 2; i++)
sp[i] = sp[i - 1] + v[i];
for(int i = 1; i < n; i++)
{
while(!dq.empty() && v[dq.back()] >= v[i])
dq.pop_back();
dq.push_back(i);
}
int mx = 0;
int st = 0;
int lg = 0;
for(int i = n; i <= n * 2 - 1; i++)
{
while(!dq.empty() && sp[dq.back()] >= sp[i])
dq.pop_back();
dq.push_back(i);
if(dq.front() <= i - n + 1)
dq.pop_front();
if(mx < sp[i + 1] - sp[dq.front()])
{
mx = sp[i + 1] - sp[dq.front()];
st = dq.front() + 1;
lg = i - dq.front() + 1;
}
}
out << mx << " " << st << " " << lg << "\n";
return 0;
}