Pagini recente » Cod sursa (job #2151387) | Cod sursa (job #1067148) | Cod sursa (job #1575465) | Cod sursa (job #1626575) | Cod sursa (job #612175)
Cod sursa(job #612175)
#include <fstream>
#include <deque>
using namespace std;
int a[200010], v[400010], n, cit, sol = -2000000000, start, finish;
deque <int> deq;
int main()
{
ifstream f("buline.in");
ofstream g("buline.out");
f >> n;
for (int i = 1; i <= n; ++i)
{
f >> a[i] >> cit;
a[i] = a[i] * (cit > 0 ? -1 : 1);
v[i] = v[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i)
v[i + n] += a[i];
for (int i = 1; i <= (n << 1); ++i)
{
if (deq.front() <= i - n) deq.pop_front();
for (; !deq.empty() && v[deq.back()] > v[i]; deq.pop_back());
deq.push_back(i);
if (sol < v[i] - v[deq.front()])
{
sol = v[i] - v[deq.front()];
start = deq.front() - 1;
finish = i - deq.front() + 1;
}
}
g << sol << ' ' << start << ' ' << finish << '\n';
g.close ();
return 0;
}